정수 삼각형 백준 1932번 DP

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

5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

n = int(input())
num_list= []
for i in range(n):
    num_list.append(list(map(int,input().split())))
for i in range(1,n):
    for j in range(len(num_list[i])):
        if j == 0:
            num_list[i][j] += num_list[i-1][j]
        elif j == len(num_list[i])-1:
            num_list[i][j] += num_list[i-1][j-1]
        else:
            num_list[i][j] += max(num_list[i-1][j-1],num_list[i-1][j])
print(max(num_list[n-1]))

어렵게 생각할 것도 없고 다이나믹프로그래밍을 생각하면서 쉽게 풀 수 있습니다.

줄을 i 줄안의 원소 인덱스를 j라고 가정하겠습니다.

일단 가장 왼쪽에 있는 원소(0)의 경우 숫자를 받아 올 수 있는 곳이 마찬가지로 끝에 있습니다. 다만 몇번째 줄인지가 다르지요[i-1][j] 그리고 가장 오른쪽에 있는 원소의 경우 받아 올 수 있는 곳은 [i-1][j-1] 밖에 없습니다.

그리고 그게 아니고 양쪽 대각선 위에서 원소를 받아 올 수 있는 곳이라면 [i-1][j-1], [i-1][j]에서 max값을 비교해서 교체를 하면 됩니다.

그리고 마지막줄(n-1)에서 가장 큰 값을 반환하면 됩니다.