[Python] 백준 1932번 문제, 정수 삼각형

<문제 링크>

 

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

---

<풀이>

 

정수 삼각형이 있는데 맨 위층에러 아래층까지 내려왔을 때 가장 큰 합이 되는 경로를 구하는 문제이다.

현재층으로 오기 위한 방법으로는 바로 대각선 대각선 위층이거나 오른쪽 대각선 위층이어야 한다.

따라서 삼각형을 리스트 형식으로 만들었을 때, 대각선 왼쪽 위층은 왼쪽 위층과 같고 오른쪽 대각선 위층은 윗층이 된다.

즉, dp[i][j]에서 왼쪽은 [i-1][j-1], 오른쪽은 바로 위층이라고 했기 때문에 [i-1][j]이다.

단, 층에서 맨 왼쪽은 대각선 왼쪽이 없기 때문에 [i-1][j]만 있으며,

맨 오른쪽은 대각선 오른쪽이 없기 때문에 [i-1][j-1]만 있다.

 

이렇게 dp에 누적합을 채우고

마지막 층에는 누적합들의 결과값들이 모여 있는데

max 메소드를 통해 누적합들 중에서 최대값을 선별한다.

 

---

<코드>

triangle[]: 삼각형 정보

dp[][]: 삼각형 누적합 저장

---

import sys

if __name__ == "__main__":
    n = int(sys.stdin.readline())
    dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
    triangle = []

    # input
    for i in range(n):
        triangle.append(list(map(int, sys.stdin.readline().split())))

    # logic
    for i in range(1, n+1):
        for j in range(1, i+1):
            if j == 1: # 맨 왼쪽 케이스
                dp[i][j] = dp[i-1][j] + triangle[i-1][j-1]
            elif i == j: # 맨 오른쪽 케이스
                dp[i][j] = dp[i-1][j-1] + triangle[i-1][j-1]
            else: # 중간에 있는 케이스
                dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i-1][j-1]

    print(max(dp[n]))