[백준/1932] 정수 삼각형 (with 파이썬)

✔ 문제

---

✔ 풀이

import sys
input = sys.stdin.readline

n = int(input())
tri = []

for _ in range(n):
    tri.append(list(map(int, input().split())))

for i in range(1, n):
    for j in range(len(tri[i])):
        if j == 0: # 가장 왼쪽인 경우
            tri[i][j] = tri[i-1][j] + tri[i][j]
        elif j == len(tri[i]) - 1: # 가장 오른쪽인 경우
            tri[i][j] = tri[i-1][j-1] + tri[i][j]
        else:
            tri[i][j] = max(tri[i-1][j-1], tri[i-1][j]) + tri[i][j]
print(max(tri[n-1]))

---

✔ 후기

1149번이랑 비슷한 문제였지만

if문으로 가장 왼쪽, 오른쪽 값을 구하는 조건을 나눠야한다.

 

처음엔 위에서 아래로 계산해 나가는 생각을 했는데 구현하는 방법은 위에서 아래보다 아래에서 위로 올라가는 방법이 더 나을 것 같다 생각이 들었다. 앞서 푼 dp 문제들만 해도 dp[i] = dp[i-1] + ... 이런 경우가 많아서 그렇게 생각했다.