[알고리즘] 동적 계획법(Dynamic Programming) - 백준 1932번 정수 삼각형

import sys
n = int(sys.stdin.readline().rstrip())
triangle = []

# 삼각형 배열 만들기
for _ in range(n):
    num = list(map(int, sys.stdin.readline().rstrip().split(' ')))
    triangle.append(num)

# 동적 계획법으로 구하기
for i in range(1, len(triangle)):
    for j in range(len(triangle[i])):
        if j == 0:
            triangle[i][j] = triangle[i-1][j] + triangle[i][j]
        elif j == len(triangle[i])-1:
            triangle[i][j] = triangle[i-1][j-1] + triangle[i][j]
        else:
            triangle[i][j] = max(triangle[i-1][j-1], triangle[i-1][j]) + triangle[i][j]

print(max(triangle[-1]))

풀이과정

1. triangle 배열 안에 위층부터 아래층으로의 숫자 배열을 넣는다.
2. [3, 8] 과 [8, 1, 0]으로 예를 들어보자. 8(j=0) 일때는 3에만 영향을 받는다. 1 일때는 3 과 8 중 큰 숫자에 영향을 받는다. 0(len(triangle[i])-1) 일때는 8 에 영향을 받는다.
3. 다시 만들어진 triangle 배열의 마지막 배열 중 가장 큰 수가 정답이다.