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

문제링크 : www.acmicpc.net/problem/1932

1932번: 정수 삼각형

9461번(파도반 수열)문제처럼 규칙을 구하는 dp문제는 접해본 적이 있지만 이렇게 최대/최소를 구하는 유형의 dp문제는 처음 풀어보았다.

주어진 예제를 통해 풀이 방법을 설명해보도록 하겠다.

맨 밑에 있는 값들을 (1) 맨 왼쪽에 있는 수 (2) 맨 오른쪽에 있는 수 (3) (1)와 (2)사이에 있는 수로 나눌 수 있다. 먼저 (1)의 경우는

으로 오른쪽 상단 한 곳을 통해서만 올 수 있기 때문에 처음 입력한 정수 삼각형 값을 저장하는 리스트를 triangle, 최댓값을 저장하는 리스트를 d라고 하면, d[i][j] = d[i-1][j] + triangle[i][j]이다. 

(2)의 경우는

으로 왼쪽 상단 한 곳을 통해서만 올 수 있기 때문에 d[i][j] = d[i-1][j-1] + triangle[i][j]이다.

(3)의 경우에 해당하는 5, 2, 6중 5에 대해서만 살펴보면

으로, 왼쪽 상단과 오른쪽 상단 두 곳을 통해서 올 수 있기 때문에 두 곳 중 최댓값을 가지는 곳에서 현재값을 더해야 최댓값을 갖게 된다. 따라서 d[i][j] = max(d[i-1][j-1], d[i-1][j]) + triangle[i][j]이다.

따라서 소스코드는 다음과 같다(별로 추천하지 않음. 맨 밑에 있는 소스코드가 좋음) .

import sys

n = int(sys.stdin.readline())
triangle = []
d = []
for _ in range(n):
    nums = list(map(int, sys.stdin.readline().rstrip().split()))
    d.append([0 for _ in range(len(nums))])
    triangle.append(nums)

d[0][0] = triangle[0][0]

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

print(max(d[n-1]))

채점 후, 다른 분들의 소스코드를 살펴보니 내가 한 것처럼 입력한 정수 삼각형 값을 저장하는 triangle과 값에 해당하는 최댓값 d리스트를 각각 만들지 않고, 하나의 리스트를 통해서 계산을 하였다. d[i][j]가 계산될 때 재사용하는 값들은 이전 줄들의 값이기 때문에 하나의 리스트를 갱신하며 계산해는 것이 공간적으로도 더욱 효율적이고 소스코드도 더욱 간결하였다.

import sys

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

for _ in range(n):
    nums = list(map(int, sys.stdin.readline().rstrip().split()))

    triangle.append(nums)

for i in range(1, n):
    for j in range(0, i+1):
        if j == 0:
            triangle[i][j] = triangle[i-1][j] + triangle[i][j]
        elif j == i:
            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[n-1]))

문제를 해결하고보니 재귀문제를 푸는 것 같다는 느낌이 들기도 했다.