백준 1932번: 정수 삼각형 (Python)

문제

위 그림은 크기가 5인 정수 삼각형의 한 모습이다. #그림 복사 잘 안 돼서 안 들고 옴. 사이트 참고.

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

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

입력

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

출력

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

 

---

 

내 풀이

N*(2N-1) 행렬 dp, value를 만든다. [i][j]: ith 행, jth 열을 의미함.

첫째 줄에 들어오는 숫자 한개는 value의 [0][N-1]에 할당되며, 이후 row가 1씩 증가할 때마다 시작하는 column의 위치가 1씩 작아지며, 2칸씩 이동하면서 채워지도록 한다.

예를 들어, 다음과 같은 input

4

1

2 3

4 5 6

7 8 9 10

			1
		2		3
	4		5		6
7		8		9		10

은 표와 같이 value에 저장한다.

dp[i][j]: [i][j]에서 시작했을 때 얻을 수 있는 최대값이라 정의한다. 그러면, 우리는 dp[0][N-1]을 구하면 된다.

재귀함수를 정의하여 top-down 방식으로 풀었다.  i == N-1인 경우(Nth row) dp[i][j] = value[i][j]라고 base case 정의.

 

코드

import sys

N = int(sys.stdin.readline())
value = [[None]*(2*N-1) for _ in range(N)]
dp = [[None]*(2*N-1) for _ in range(N)]
for i in range(N):
    temp = list(map(int, sys.stdin.readline().split()))
    for j in range(len(temp)):
        value[i][N-1-i+2*j] = temp[j]

def triangle_max(i, j):
    if i == N-1:
        dp[i][j] = value[i][j]
        return dp[i][j]
    
    if dp[i][j]:
        return dp[i][j]
    
    dp[i][j] = value[i][j] + max(triangle_max(i+1, j-1), triangle_max(i+1, j+1))
    return dp[i][j]

print(triangle_max(0, N-1))

 

---

 

다른 분의 풀이: https://www.acmicpc.net/source/33967131

세 사람이 같은 길을 가도 스승이 있는 법인데, 백준에는 공개된 코드가 매우 많으니 스승이 참 많다. 내 풀이보다 여러모로 간단하며 좋은 코드를 이해해보자.

 

코드

import sys
input=sys.stdin.readline

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

for i in range(1,n):
    tri[i][0]+=tri[i-1][0]     #가장자리 구해놓기
    tri[i][-1]+=tri[i-1][-1]

for i in range(2,n):
    for j in range(1,len(tri[i])-1):   #점화
        tri[i][j]+=max(tri[i-1][j-1],tri[i-1][j])
        
print(max(tri[-1]))

tri에 한 줄마다 자연스러운 방식으로 자료를 넣었다. 앞에서 예시로 든 삼각형은

1	out of range	out of range	out of range
2	3	out of range	out of range
4	5	6	out of range
7	8	9	10

와 같이 저장된다.

STEP1) 가장자리(j=0 or j=-1)로 오는 경로는 1가지(맨 왼쪽: 왼쪽->왼쪽->...->왼쪽 / 맨 오른쪽: 오른쪽->오른쪽->...->오른쪽)이므로, i에 대한 for문을 돌려 tri[i][j] = tri[i][j] += tri[i-1][j]로 구할 수 있다.이후 tri[i][j]를 [0][0]부터 [i][j]까지 오면서 가질 수 있는 최대값이라 정의하였다. 

1	out of range	out of range	out of range
3	4	out of range	out of range
7	5	10	out of range
14	8	9	10

STEP2) i=2부터 시작하여, 1=<j<i인 범위에 대해 왼쪽에서 오는 경우, 오른쪽에서 오는 경우 중 큰 경우를 선택하면 된다.

1	out of range	out of range	out of range
3	4	out of range	out of range
7	9	10	out of range
14	17	19	20

STEP3) 마지막으로, 마지막 행에서 최대값을 찾아 출력하면 된다.

 

이 풀이의 장점:

쓸데없이 리스트의 size를 내 풀이마냥 늘리지 않았으며, input 값을 저장한 곳에서 바로 동적 계획법을 통해 값을 계산하여 메모리를 아낄 수 있다.