[백준] 1932 - 정수 삼각형 (DP)

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

1932번: 정수 삼각형

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
answer = [list() for _ in range(n)]
index = 0
for i in arr[n - 1]:
    answer[0].append(i)
 
for a in arr[n - 2::-1]:
    index += 1
    for i in range(len(a)):
        answer[index].append(a[i] + max(answer[index - 1][i], answer[index - 1][i + 1]))
 
print(answer[-1][0])

간단한 DP문제이다.

이 문제를 접근할 때는 삼각형의 아래쪽(숫자가 많은 쪽)에서부터 접근하는 것이 더 편하다고 생각한다. 뭐 반대로 해도 크게 다르지는 않겠지만..

아래쪽에서부터 위로 올라가며, 한 줄 아래의 숫자 중 어떤걸 선택해야 최댓값이 될지 선택하면 올라가는 방식이다.