[백준] 1932번 > 정수 삼각형

www.acmicpc.net/problem/1932

1932번: 정수 삼각형

문제

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

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

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

입력

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

출력

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

예제 입력 1

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

예제 출력 1

30

 

---

풀이

점화식을 세우고 규칙을 도출해야한다. DP문제이므로

먼저 각 행의 첫번째 원소는 윗 행의 첫번째 원소와의 합이다. 마지막 원소도 동일하다.

 

다음과 같이 묶여있는 것이다. 이유는 

아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

라는 조건 때문이다. 따라서 아래와 같이 바뀔 것이다.

이제 내부의 삼각형만 점화식을 세우면 되는데 점화식은 다음과 같다.

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

이를 코드로 나타낸 것이다.

n = int(input())
triangle = [list(map(int, input().split())) for _ in range(n)]
for i in range(1, n):
    for j, p in enumerate(triangle[i]):
        if j != 0 and j != i:
            triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
    triangle[i][0] += triangle[i-1][0]
    triangle[i][-1] += triangle[i-1][-1]
print(max(triangle[-1]))

첫번째와 마지막 원소가 아닌경우에만 점화식을 적용시켜주었고,

첫번째와 마지막은 그 윗값과 바로 더해주었다.