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

 

n = int(input())

num = []
for i in range(n):
    num.append(list(map(int, input().split())))

for i in range(n-1, 0, -1):
    for j in range(len(num[i-1])):
        num[i-1][j] += max(num[i][j], num[i][j+1])
        
print(num[0][0])

 

코드 설명

먼저 주어진 삼각형 모양의 수를 입력을 받는다. 삼각형의 아래부분 부터 반복문을 시작한다. 내부 반복문은 층의 수만큼 반복한다.

위층에 있는 수와 아래 층의 왼쪽, 오른쪽의 수에서 더한 값이 큰 값을 선택한다. 끝까지 반복하면 num[0][0] 리스트에 가장 큰 값이 저장되어 있다.

 

Point : 아래부터 시작하여 위로 가는 bottom-up 기법을 활용한다. 예를 들어 4층의 수중 큰 것을 구하기 위해 5층의 왼쪽 오른쪽 중 하나를 선택하여 더한 값중 큰 값을 선택하여 누적 시키는 방식으로 결과를 구할 수 있다.