[백준 알고리즘] 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

풀이

이 문제는 max함수를 사용하여 각각의 층을 내려오면서 합의 최대 값을 구하는 문제로써 dp을 사용하여 문제를 풀어야 한다.

dp문제를 풀게 되면 가장 먼저 규칙을 찾고 점화식을 구하면 쉽게 문제를 풀 수 있다.

이 문제에 점화식을 구하게 되면 다음과 같다.

dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + dp[i][j]

점화식을 구한 과정은 다음과 같다.

가장 이중 배열을 사용하여 위에 있는 숫자 값과 자기 자신 값의 합을 자기 자신 값으로 바꾸며 한층 한층 내려가면서 계산하고

위에 있는 값이 두개인 경우 max함수를 사용하여 두 개의 값을 비교해 큰 값과 더하면 된다.

이 과정을 처음 입력한 삼각형의 높이 만큼 반복한다.

그림을 통해 설명 하면 아래 그림같이 나타 낼 수 있다.

코드

import sys

hight = int(sys.stdin.readline())
triangle = []

for _ in range(hight):
    triangle.append(list(map(int, sys.stdin.readline().split())))

k = 2

# 점화식: dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + dp[i][j]
for i in range(1, hight):
    for j in range(k):
        if j == 0:
            triangle[i][j] = triangle[i][j] + triangle[i-1][j]
        elif i == j:
            triangle[i][j] = triangle[i][j] + triangle[i-1][j-1]
        else:
            triangle[i][j] = max(triangle[i-1][j-1],
                                 triangle[i-1][j]) + triangle[i][j]
    k += 1
print(max(triangle[hight-1]))