[백준] 1932 '정수 삼각형' 파이썬(python)

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

1932번: 정수 삼각형

n = int(input())
dp = []
for i in range(n):
    dp.append(list(map(int, input().split())))
k = 2
for i in range(1, n):
    for j in range(k):
        if j==0:
            dp[i][j] = dp[i][j] + dp[i-1][j]
        elif i == j:
            dp[i][j] = dp[i][j] + dp[i-1][j-1]
        else :
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + dp[i][j]
    k+=1

print(max(dp[n-1]))

Point

• dp테이블을 활용한 DP 문제

i/j	0	1	2	3	4
0	7
1	3	8
2	8	1	0
3	2	7	4	4
4	4	5	2	6	5

• 합산을 해나가는 것으로서 합산에는 세 가지 경우로 나눌 수 있다.
• 본래는 삼각형인 것을 표로 만들어 넣은 것으로 잊질 말아야 한다.
• 첫번째는 j = 0이면 오른쪽 대각선 위 값을 가져오는 것. 즉 dp[i][j] = dp[i-1][j] + dp[i][j]
• 두번째는 j = i 인 경우로서 왼쪽 대각선의 값을 가져오는 것. 즉 dp[i][j] = dp[i-1[j-1] + dp[i][j]
• 마지막은 나머지 경우로서 중앙에 있는 값들인데 이들은 왼쪽 대각선 위 혹은 오른쪽 대각선 위 중 값이 큰 것을 골라야 한다. 따라서 dp[i][j] = max(dp[i-1][j], dp[i-1[j-1]) + dp[i][j]
• 이번 dp 문제는 표를 만들어서 그에 대한 케이스로 나누어 푸는 문제였다.