[S1] 백준 1932 - 정수 삼각형 (Python3)

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

---

해결방법

정수 삼각형의 맨 아래층부터 위층으로 올라간다. 각 행의 원소를 순회하면서, 현재 위치의 정수와 현재 위치의 왼쪽 아래 정수와 오른쪽 아래 정수 중 더 큰 값과의 합을 DP table에 저장한다. ( max(왼쪽아래 정수, 오른쪽아래 정수) + 현재위치 정수 )

풀이👀

1. 주어진 정수 삼각형에서 아래층부터 위층으로 올라가며 각 행의 원소를 순회한다.
2. 각 행의 원소를 순회하면서 현재 위치의 정수에 다음 행(아래층)의 왼쪽 대각선 정수와 오른쪽 대각선 정수 중 더 큰 값을 더해가며 최대 합을 계산한다.
3. 모든 행을 순회하면서 이를 맨 위층까지 반복한다.
4. 최종적으로 맨 위층의 최대 합을 반환한다.

---

코드🐱‍👓

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

# DP테이블 초기화
dp = [[0] * n for _ in range(n)]

# 맨 아래층의 값으로 초기화
dp[n - 1] = triangle[n - 1]

# 아래층부터 위층으로 올라가며 최대 합 계산
for i in range(n - 2, -1, -1):
    for j in range(i + 1):
        dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]

print(dp[0][0])

---

DP table 변화

예제입력으로 주어진 정수 삼각형에 대해 코드를 실행했을 때의 모든 변화를 살펴보자.

1. 초기 상태:
           0
         0  0
       0  0  0
     0  0  0  0
   4  5  2  6  5
2. 첫 번째 반복문 실행 (아래층부터 위층으로):
   • i = 3일 때:
     • 두 번째 반복문 실행 (각 행의 원소를 순회):
       • j = 0일 때:
         • dp[3][0] = max(dp[4][0], dp[4][1]) + triangle[3][0] = max(4, 5) + 2 = 7
       • j = 1일 때:
         • dp[3][1] = max(dp[4][1], dp[4][2]) + triangle[3][1] = max(5, 2) + 7 = 12
       • j = 2일 때:
         • dp[3][2] = max(dp[4][2], dp[4][3]) + triangle[3][2] = max(2, 6) + 4 = 10
       • j = 3일 때:
         • dp[3][3] = max(dp[4][3], dp[4][4]) + triangle[3][3] = max(6, 5) + 4 = 10
3. 첫 번째 반복문 실행 결과:
                0
             0    0
         0     0    0
     9    12   10   10  
   4    5     2     6    5
   
   
4. 두 번째 반복문 실행 (아래층부터 위층으로):
   • i = 2일 때:
     • 두 번째 반복문 실행 (각 행의 원소를 순회):
       • j = 0일 때:
         • dp[2][0] = max(dp[3][0], dp[3][1]) + triangle[2][0] = max(9, 12) + 8 = 20
       • j = 1일 때:
         • dp[2][1] = max(dp[3][1], dp[3][2]) + triangle[2][1] = max(12, 10) + 1 = 13
       • j = 2일 때:
         • dp[2][2] = max(dp[3][2], dp[3][3]) + triangle[2][2] = max(10, 10) + 0 = 10
5. 두 번째 반복문 실행 결과:
                0
             0    0
        20   13   10
     9    12   10   10
   4    5     2     6    5
   
   
6. 세 번째 반복문 실행 (아래층부터 위층으로):
   • i = 1일 때:
     • 두 번째 반복문 실행 (각 행의 원소를 순회):
       • j = 0일 때:
         • dp[1][0] = max(dp[2][0], dp[2][1]) + triangle[1][0] = max(20, 13) + 3 = 23
       • j = 1일 때:
         • dp[1][1] = max(dp[2][1], dp[2][2]) + triangle[1][1] = max(13, 10) + 8 = 21
7. 세 번째 반복문 실행 결과:
                0
            23   21
        20   13   10
     9    12   10   10
   4    5     2     6    5
   
   
8. 네 번째 반복문 실행 (아래층부터 위층으로):
   • i = 0일 때:
     • 두 번째 반복문 실행 (각 행의 원소를 순회):
       • j = 0일 때:
         • dp[0][0] = max(dp[1][0], dp[1][1]) + triangle[0][0] = max(23, 21) + 7 = 30
9. 네 번째 반복문 실행 결과:
               30
            23   21
        20   13   10
     9    12   10   10
   4    5     2     6    5

따라서 정답은 30이다.