[백준] 1932번: 정수 삼각형 - python

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

처음 아이디어 

왼쪽과 오른쪽 인자를 비교하여 큰 것을 저장하며 값을 저장한다.

 

틀린이유

작은 것을 선택했을때 마지막에 값이 더 큰 경우의 수가 존재한다.

n = int(input())

arr = []
dp = [0] * (n+1)
for i in range(n):
    arr.append(list(map(int, input().split())))


dp[0] = arr[0][0]
high = 0
for i in range(1,n):
    if arr[i][high+1] > arr[i][high]:
        high +=1
        dp[i] = dp[i-1] + arr[i][high]
    else:
        dp[i] = dp[i-1] + arr[i][high]
    print(dp)
print(dp[i])

 

다시 생각한 아이디어

n 깊이까지의 최대값을 계속 저장하여 마지막까지 간다.

갑자기 생각난건데 dfs, 브루드포스로도 푸는게 가능할 것 같다. 그건 나중에 하고 작성해봤다.

 

값 자체에서 토마토 문제 처럼 인덱스를 사용하여 최대값을 계속해서 저장해나가는 식으로 풀었다. 인덱스 맨 첫번째거나 마지막인 경우는 그 전 시작, 모서리 부분을 값에 저장하고 그 외 인덱스 안쪽 부분은 두개 값을 비교하여 큰 값을 저장해나가는 방식으로 DP를 구현했다. 그리고 최종 가장 큰 값을 출력하는 코드이다.

n = int(input())

dp = []

for i in range(n):
    dp.append(list(map(int, input().split())))

for i in range(1, n):
    for j in range(i+1):
        if j == 0:
            dp[i][j] += dp[i-1][j]
        elif j == i:
            dp[i][j] += dp[i-1][j-1]
        else:
            dp[i][j] += max(dp[i-1][j], dp[i-1][j-1])

print(max(map(max, dp)))

 

완성