백준 1932 - 정수 삼각형 [파이썬]

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

1932번: 정수 삼각형

---

풀이 과정

정수 삼각형에 들어있는 요소를 담는 배열을 위의 그림과 같이 생각하면

 

d[i][0] = d[i-1][0] + p[i][0]

d[i][k] = max(d[i-1][k-1] + p[i][k], d[i-1][k] + p[i][k]) (1  <= k <= i-1)

d[i][i] = d[i-1][i-1] + p[i]

 

다음과 같은 점화식이 성립하고 이를 통해 문제를 해결하면 된다

 

 

 

---

소스 코드

import sys

n = int(sys.stdin.readline())
p = []
d = []

for i in range(n):
    p.append(list(map(int, sys.stdin.readline().split())))
    if i == 0:
        d.append([p[0][0]])
        continue
    d.append([d[i-1][0] + p[i][0]])
    for k in range(1, i):
        d[i].append(max(d[i - 1][k - 1], d[i - 1][k]) + p[i][k])
    d[i].append(d[i-1][i-1] + p[i][i])

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