[백준] 1932 정수 삼각형

문제

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

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.
맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

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

출력

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

내 풀이

import sys
input = sys.stdin.readline

triangle = []

n = int(input())
for _ in range(n):
    list1 = list(map(int, input().split()))
    triangle.append(list1)
    
dp = [0]*n

dp[0] = triangle[0][0]

j = 0
for i in range(1, n):
    dp[i] = max(dp[i-1]+triangle[i][j], dp[i-1]+triangle[i][j+1])
    if triangle[i][j] < triangle[i][j+1]:
        j += 1
    else:
        pass
    
print(max(dp)) 

처음에는 DP로 풀어야 하는 문제인 것은 파악했지만 단순에 다음 행에서 고를 수 있는 가장 큰 수를 택하는 방식으로 풀었더니 끝까지 갔을 때 합이 최대가 되는 경로를 놓치게 되어서 틀렸다. 아래는 다른 풀이를 참고해서 다시 푼 정답 코드이다.

import sys
input = sys.stdin.readline

dp = []

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

코멘트

당장 다음 행에서 가장 큰 수를 고르는 것이 중요한 게 아니라, 바로 다음 행이 작은 수이더라도 끝까지 갔을 때 큰 수들이 많이 있는 최대 합을 찾아내는 것이 중요한 문제인데 그것을 어떻게 구현해야 할지 생각나지가 않았다ㅠ

다른 풀이를 참고해보니 위와 같은 방식로 풀면 각 행에서 계산하는 모든 경우의 수를 따지면서 끝까지 갔을 때 최대 합을 찾아 낼 수 있었다. 가장 첫 열과 가장 마지막 열은 그들끼리만 더하면 되고, 중간에 있는 열들은 왼쪽에서 더해지는 수와 오른쪽에서 더해지는 수 중 더 큰 수를 골라서 연산을 하면 되는 것이다.

References

https://www.acmicpc.net/problem/1932
https://coooco.tistory.com/105
https://animoto1.tistory.com/entry/%EB%B0%B1%EC%A4%80-1932-%EC%A0%95%EC%88%98-%EC%82%BC%EA%B0%81%ED%98%95-%ED%8C%8C%EC%9D%B4%EC%8D%AC-Python