백준 알고리즘 - 정수 삼각형(1932번)[Python]

문제

문제 상황

- 선택을 하나 했을 때, 다음 선택을 할 수 있는 경우는 2가지 뿐이고 한 선택이 다른 선택에 영향을 주며 그 상황에서 최대 값 찾는 문제이므로 DP를 사용한다. 

 

해결 전략

- 최대값을 담는 dp 리스트를 따로 만들어 문제의 dp를 담는다. 

코드 

# dp[i][j] = i행 j열 까지의 합 중 최대가 되는 경우의 합
# a[i][j] = 주어진 삼각형을 담는 리스트
n = int(input())
a = [[0] for _ in range(n)]
for i in range(n):
    a[i] = list(map(int, input().split())) 
dp = [[0]*n for _ in range(n)]
dp[0][0] = a[0][0]
for i in range(1, n):
    for j in range(i+1):
        if j < 1 :
            dp[i][j] = dp[i-1][j] + a[i][j]
        elif j > i :
            dp[i][j] = dp[i-1][j-1] + a[i][j]
        else :
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j]
print(max(dp[n-1]))

 

해설

새로 학습한 것 & 실수

- 배열을 하나만 쓰면 안된다. 하나의 선택지가 두가지 경우에 영향을 주기 때문에 배열이 갱신되면 결과를 바꿔버린다.