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

문제

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

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

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

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

 

코드

tri = []
dp = []
n = int(input())
for i in range(n):
    tri.append(list(map(int, input().split())))
    dp.append([None]*(i+1))
dp[0][0] = tri[0][0]
for i in range(1, n):
    for j in range(i+1):
        if j == 0:
            dp[i][j] = dp[i-1][j]+tri[i][j]
        elif j == i:
            dp[i][j] = dp[i-1][j-1]+tri[i][j]
        else:
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + tri[i][j]
print(max(dp[n-1]))

 

풀이

간단히 생각해도 모든 경로는 $$2^{n-1}$$개이므로 이를 전부 고려하는 것은 불가능에 가깝다. 따라서 바로 동적 계획법으로 간다.

다른 블로그들과 여러 DP 문제를 풀면서 생긴 노하우인데, DP는 원래 배열과 같은 크기의 배열이 요구되는 것 같다. 그래서 이번에는 무작정 삼각형 구조를 그대로 본딴 DP 배열을 만들어보았다.

우선 맨 꼭대기 시작은 동일하니 초기항을 맨 꼭대기로 정해줄 수 있다.

바로 아랫줄은 두 칸까지의 합이 확정되므로 맨 꼭대기 칸 수 + 해당 칸 수 그대로 DP 배열에 저장해줄 수 있다.

세번째 줄은 조금 달라진다. 물론 양 끝의 칸들은 확정되므로 이전처럼 할 수 있지만, 그 사이 중간의 칸이 문제다.

 

    ㅁ

   1  2

ㅁ ■ ㅁ

 

중간의 검은 네모 칸이 문제가 된다.

검은 네모 칸으로 가는 방법은 처음-1번칸-검은네모, 처음-2번칸-검은네모 두 방법이 있다.

그래서 1번칸, 2번칸 중 그 칸까지의 합이 가장 큰 녀석을 고른 후, 여기에다가 검은네모칸의 수를 더해주어서 검은네모칸까지의 최대 합을 구할 수 있다.

4번째 줄부터는 이런 검은네모칸이 점점 많아지는데, 똑같은 방법으로 해주면 된다.

그리고 맨 마지막 줄의 합들 중에서의 가장 큰 합을 출력하면 된다.