[백준] 1932 정수 삼각형

문제

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

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

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

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

예제 입력

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

예제 출력

30

풀이

RGB 계단 문제와 유사하다. 단순 동작 원리를 파악하여 구현한 코드와, 점화식을 이용한 코드를 알아보자. 단순 동작 원리를 파악해 구현한 코드도 어차피 점화식을 만족하게 되어있다.

단순 동작 원리 파악하여 구현
인덱스의 관계를 이용해 접근했다. 삼각형을 위에서부터 한줄씩 배열로 만들어서 2차원 배열에 저장하였다. i 는 2차원 배열의 인덱스, j는 하나의 줄(배열)의 인덱스

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

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

점화식을 이용하여 구현
f(m,n)
= m번째 줄의 n번째 값이 가질 수 있는 최대값
= MAX(f(m-1, n-1), f(m-1, n)) (n이 0이거나 len(m)-1 인 경우는 별도 계산)

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

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

동일한 코드가 나오는 것을 볼 수 있다. dp 문제에선 점화식을 항상 생각해야겠다.