2. 백준 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번째 줄까지 정수 삼각형이 주어진다.

 

출력

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

예제 입력 1 복사

 

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

 

예제 출력 1 복사

30

---

아이디어(접근 방법)

1. 동적 계획법(Dynamic Programming) 개념

• 점화식을 세우고, 작은 문제부터 차근차근 답을 구해가며 최종적으로 큰 문제의 답을 구하는 방식입니다.
• 보통 “정수 삼각형” 문제는 위에서부터 아래로 내려가면서 DP 테이블을 채우는 방법과, 아래에서부터 위로 올라가면서 DP 값을 갱신하는 방법, 두 가지가 많이 사용됩니다.

2. 아래에서부터 위로 올라가는 방식

1. 삼각형의 맨 아래층부터 시작하여, 바로 위의 층에 있는 각 원소에 대하여 “현재 위치에서 만들 수 있는 최대 합”을 갱신합니다.
2. 예를 들어, 삼각형의 i번째 줄, j번째 원소(triangle[i][j]\text{triangle}[i][j]triangle[i][j])에 대해triangle[i][j]=triangle[i][j]+max⁡(triangle[i+1][j],triangle[i+1][j+1])\text{triangle}[i][j] = \text{triangle}[i][j] + \max(\text{triangle}[i+1][j], \text{triangle}[i+1][j+1])triangle[i][j]=triangle[i][j]+max(triangle[i+1][j],triangle[i+1][j+1])와 같이 갱신합니다.
3. 맨 위 줄(인덱스 0)까지 반복해서 올라오면, triangle[0][0]\text{triangle}[0][0]triangle[0][0]에 최댓값 경로의 합이 저장됩니다.

장점

• 별도의 추가 메모리 DP 배열을 만들지 않고, 입력 삼각형 배열 자체를 갱신해가며 최댓값을 구할 수 있습니다.

---

예시 설명

주어진 예시 삼각형을 생각해 봅시다.

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

맨 아래줄부터 시작해 위로 한 단계씩 올라가며 배열을 갱신합니다.

1. 가장 아래 줄: [4, 5, 2, 6, 5]
   • 아직은 그대로 두고, 바로 위 층부터 갱신을 시작합니다.
2. 네 번째 줄(인덱스 3) 갱신:
   • 삼각형[3][0] = 2 + max(4, 5) = 2 + 5 = 7
   • 삼각형[3][1] = 7 + max(5, 2) = 7 + 5 = 12
   • 삼각형[3][2] = 4 + max(2, 6) = 4 + 6 = 10
   • 삼각형[3][3] = 4 + max(6, 5) = 4 + 6 = 10
   • 이 과정을 거치면 네 번째 줄이 [7, 12, 10, 10]으로 변합니다.
3. 세 번째 줄(인덱스 2) 갱신:
   • 삼각형[2][0] = 8 + max(7, 12) = 8 + 12 = 20
   • 삼각형[2][1] = 1 + max(12, 10) = 1 + 12 = 13
   • 삼각형[2][2] = 0 + max(10, 10) = 0 + 10 = 10
   • 세 번째 줄은 [20, 13, 10]으로 바뀝니다.
4. 두 번째 줄(인덱스 1) 갱신:
   • 삼각형[1][0] = 3 + max(20, 13) = 3 + 20 = 23
   • 삼각형[1][1] = 8 + max(13, 10) = 8 + 13 = 21
   • 두 번째 줄은 [23, 21]로 갱신됩니다.
5. 첫 번째 줄(인덱스 0) 갱신:
   • 삼각형[0][0] = 7 + max(23, 21) = 7 + 23 = 30
   • 이제 삼각형의 맨 위는 30이 됩니다. 이 값이 최댓값 경로의 합입니다.

---

코드 구현

def solve():
    import sys
    input = sys.stdin.readline  # 백준에서 빠른 입력 받는 용도로 주로 사용

    n = int(input().strip())  # 삼각형의 크기 입력
    triangle = []

    # 삼각형 리스트 생성
    for _ in range(n):
        row = list(map(int, input().split()))
        triangle.append(row)

    # 맨 아래층부터 시작하여 바로 위층 값을 갱신해가는 방식
    for i in range(n - 2, -1, -1):        # n-2부터 0까지 거꾸로(위로) 이동
        for j in range(len(triangle[i])):  # i번째 층의 각 원소에 대해
            triangle[i][j] += max(triangle[i + 1][j], triangle[i + 1][j + 1])
    
    # 최종적으로 맨 위(0, 0)에 최댓값 경로의 합이 저장됨
    print(triangle[0][0])

코드 동작 설명

1. 입력 받기
   • nnn을 입력받고,
   • 이후 nnn줄에 걸쳐 각 층의 정수를 입력받아 triangle 2차원 리스트로 저장합니다.
2. DP 갱신
   • 가장 아래층(인덱스 n−1n-1n−1)은 그대로 두고, 그 바로 위층(인덱스 n−2n-2n−2)부터 시작하여 최상층(인덱스 0)까지 거꾸로 올라가면서 다음과 같이 갱신합니다: triangle[i][j]=triangle[i][j]+max⁡(triangle[i+1][j],triangle[i+1][j+1])\text{triangle}[i][j] = \text{triangle}[i][j] + \max(\text{triangle}[i+1][j], \text{triangle}[i+1][j+1])triangle[i][j]=triangle[i][j]+max(triangle[i+1][j],triangle[i+1][j+1])
   • 즉, 아래층에서 가능한 두 경로 중 더 큰 합을 현재 층의 값과 더해서 저장합니다.
3. 결과 출력
   • 최종적으로 맨 위 위치(triangle[0][0]\text{triangle}[0][0]triangle[0][0])가 우리가 구하고자 하는 최대 합이 됩니다.
   • 이를 출력하고 종료합니다.

---

복잡도 분석

• 삼각형의 크기를 nnn이라 할 때,
  • 입력받는 과정은 O(n2)O(n^2)O(n2) (삼각형이 1 + 2 + ... + n = n(n+1)2\frac{n(n+1)}{2}2n(n+1)​개의 원소)
  • DP 갱신 과정도 마찬가지로 O(n2)O(n^2)O(n2)
• 따라서 전체 시간 복잡도는 O(n2)O(n^2)O(n2)입니다.
• 메모리는 문제에서 주어진 최대 크기 500×500(대략 25만) 정도까지 충분히 처리 가능합니다.

---

결론

• 삼각형의 맨 아래층부터 올라오면서 갱신하는 방식의 동적 계획법을 사용하여 문제를 간단히 해결할 수 있습니다.
• 최댓값 경로의 합은 최종적으로 삼각형의 맨 윗값(triangle[0][0]\text{triangle}[0][0]triangle[0][0])에 저장됩니다.

이로써 주어진 예제를 포함한 모든 경우에 대해, 최댓값 경로의 합을 효율적으로 구할 수 있습니다.