백준 정수 삼각형 1932 C++

백준 정수 삼각형 1932 C++

문제 설명

문제

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

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

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

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

출력

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

---

테스트케이스

입력

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

출력

30
    

---

문제 작동원리

이 문제는 위에서부터 한 칸씩 내려오면서,

• 한 단계 내려갈 때 왼쪽 대각선 또는 오른쪽 대각선 방향으로만 이동할 수 있습니다.
• 가능한 모든 경로의 합 중 가장 큰 값을 찾아야 합니다.

예를 들어, 위 예시에서

• `7 → 3 → 8 → 7 → 5` 의 합은 `7 + 3 + 8 + 7 + 5 = 30` 입니다.
• 다른 경로를 가면 합이 작아집니다. 예를 들어 `7 → 8 → 0 → 4 → 6` 은 `25`가 됩니다.

즉, 문제는 출발점에서부터 도착점까지 가능한 경로 중 합이 최대인 값을 찾는 것입니다.

---

전체코드

#include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
    int N;
    cin >> N;
    int arr[501][501] = {0};
    int sumArr[501][501] = {0};
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < i + 1; j++)
        {
            cin >> arr[i][j];
        }
    }
    sumArr[0][0] = arr[0][0];
    for(int i = 1; i < N; i++)
    {
        for(int j = 0; j < i + 1; j++)
        {
            if(j == 0) // 맨 왼쪽
                sumArr[i][j] = arr[i][j] + sumArr[i-1][j];
            else if (j == i) // 맨 오른쪽
                sumArr[i][j] = arr[i][j] + sumArr[i-1][j-1];
            else // 중간
                sumArr[i][j] = max(sumArr[i-1][j-1], sumArr[i-1][j]) + arr[i][j];
        }
    }
    cout << *max_element(sumArr[N-1], sumArr[N-1] + N) << endl;
    return 0;
}
    

---

---

아이디어

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

이 문제는 삼각형 형태의 숫자 배열이 주어졌을 때, 위에서 아래로 내려가면서 얻을 수 있는 경로의 합 중 최대값을 구하는 문제입니다.
이를 해결하기 위해 다음 세 가지 원칙을 사용합니다.

• 맨 왼쪽 값 업데이트 원칙
  현재 행의 맨 왼쪽 값은, 바로 위 행의 맨 왼쪽 값에서만 내려올 수 있습니다. 따라서 `sumArr`의 해당 위치 값은 바로 위 맨 왼쪽 값에 현재 값을 더한 값으로 업데이트합니다.
• 맨 오른쪽 값 업데이트 원칙
  현재 행의 맨 오른쪽 값은, 바로 위 행의 맨 오른쪽 값에서만 내려올 수 있습니다. 따라서 `sumArr`의 해당 위치 값은 바로 위 맨 오른쪽 값에 현재 값을 더한 값으로 업데이트합니다.
• 중간 값 업데이트 원칙
  현재 행의 중간 값들은, 바로 위 행의 왼쪽 값 또는 오른쪽 값에서 내려올 수 있습니다. 이때 두 값 중 더 큰 값을 선택하여, 그 값에 현재 값을 더해 `sumArr`에 업데이트합니다.

---

arr와 sumArr 생성 및 초기 상태 설명

`arr` 배열에는 문제에서 주어진 삼각형 숫자 배열이 그대로 저장됩니다.
`sumArr` 배열은 DP(Dynamic Programming) 방식으로 각 위치까지의 경로 합의 최대값을 저장하는 용도로 사용됩니다.
즉, `sumArr[i][j]`는 i번째 행, j번째 열에 도착했을 때 가능한 최대 경로의 합을 의미합니다.
처음에는 모든 값을 0으로 초기화합니다.
이는 아직 어떠한 경로 계산도 이루어지지 않았음을 의미하며, 앞으로 한 칸씩 값을 채워나가게 됩니다.

---

초기 상태
`arr`

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

`sumArr`

      0
     0 0
    0 0 0
   0 0 0 0
  0 0 0 0 0
    

---

값 업데이트 과정 (한 칸씩, 괄호 표시)

---

1단계: 첫 번째 값 업데이트

삼각형의 꼭대기 값인 `arr[0][0]`에서 시작합니다.
`sumArr[0][0]`은 초기값 0에서, `arr[0][0]`인 7을 더해 7로 업데이트됩니다.
이 값은 시작점이므로 그대로 저장됩니다.

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

`sumArr`

      7
     0 0
    0 0 0
   0 0 0 0
  0 0 0 0 0
    

---

2단계: 두 번째 행 왼쪽 값(3) 업데이트

`arr[1][0]`은 맨 왼쪽 값이므로, 이전 행의 맨 왼쪽 값 `sumArr[0][0]`에서만 내려올 수 있습니다.
따라서 `sumArr[1][0] = sumArr[0][0] + arr[1][0] = 7 + 3 = 10`이 됩니다.

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

`sumArr`

      7
     10  0
    0  0  0
   0  0  0  0
  0  0  0  0  0
    

---

3단계: 두 번째 행 오른쪽 값(8) 업데이트

`arr[1][1]`은 맨 오른쪽 값이므로, 이전 행의 맨 오른쪽 값 `sumArr[0][0]`에서만 내려올 수 있습니다.
따라서 `sumArr[1][1] = sumArr[0][0] + arr[1][1] = 7 + 8 = 15`가 됩니다.

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

`sumArr`

      7
     10 15
    0  0  0
   0  0  0  0
  0  0  0  0  0
    

---

4단계: 세 번째 행 왼쪽 값(8) 업데이트

`arr[2][0]`은 맨 왼쪽 값이므로, 이전 행의 맨 왼쪽 값 `sumArr[1][0]`에서만 내려올 수 있습니다.
`sumArr[2][0] = sumArr[1][0] + arr[2][0] = 10 + 8 = 18`이 됩니다.

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

`sumArr`

      7
     10 15
    18  0  0
   0  0  0  0
  0  0  0  0  0
    

---

5단계: 세 번째 행 중간 값(1) 업데이트

`arr[2][1]`은 중간 값이므로, 이전 행에서 두 경로가 내려올 수 있습니다.

• 왼쪽 위 값: `sumArr[1][0] = 10`
• 오른쪽 위 값: `sumArr[1][1] = 15`

이 중 더 큰 값 15를 선택하여 현재 값 1을 더합니다.
`sumArr[2][1] = 15 + 1 = 16`이 됩니다.

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

`sumArr`

      7
     10 15
    18 16  0
   0  0  0  0
  0  0  0  0  0
    

---

6단계: 세 번째 행 오른쪽 값(0) 업데이트

`arr[2][2]`은 맨 오른쪽 값이므로, 이전 행의 맨 오른쪽 값 `sumArr[1][1]`에서만 내려올 수 있습니다.
`sumArr[2][2] = 15 + 0 = 15`가 됩니다.

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

`sumArr`

      7
     10 15
    18 16 15
   0  0  0  0
  0  0  0  0  0
    

---

7단계: 네 번째 행 왼쪽 값(2) 업데이트

`arr[3][0]`은 맨 왼쪽 값입니다.
따라서 `sumArr[3][0] = sumArr[2][0] + 2 = 18 + 2 = 20`이 됩니다.

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

`sumArr`

      7
     10 15
    18 16 15
    20  0  0  0
   0  0  0  0  0
    

---

8단계: 네 번째 행 중간 값(7) 업데이트

`arr[3][1]`은 중간 값입니다.

• 왼쪽 위 값: `sumArr[2][0] = 18`
• 오른쪽 위 값: `sumArr[2][1] = 16`

더 큰 값 18을 선택하여 현재 값 7을 더합니다.
`sumArr[3][1] = 18 + 7 = 25`가 됩니다.

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

`sumArr`

      7
     10 15
    18 16 15
    20 25  0  0
   0  0  0  0  0
    

---

9단계: 네 번째 행 중간 값(4) 업데이트

`arr[3][2]`도 중간 값입니다.

• 왼쪽 위 값: `sumArr[2][1] = 16`
• 오른쪽 위 값: `sumArr[2][2] = 15`

더 큰 값 16을 선택하여 현재 값 4을 더합니다.
`sumArr[3][2] = 16 + 4 = 20`이 됩니다.

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

`sumArr`

      7
     10 15
    18 16 15
    20 25 20  0
   0  0  0  0  0
    

---

10단계: 네 번째 행 오른쪽 값(4) 업데이트

`arr[3][3]`은 맨 오른쪽 값입니다.
`sumArr[3][3] = sumArr[2][2] + 4 = 15 + 4 = 19`가 됩니다.

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

`sumArr`

      7
     10 15
    18 16 15
    20 25 20 19
   0  0  0  0  0
    

---

결론

1. 현재 행의 맨 왼쪽 값은, 바로 위 행의 맨 왼쪽 값에서만 내려올 수 있습니다.
2. 현재 행의 맨 오른쪽 값은, 바로 위 행의 맨 오른쪽 값에서만 내려올 수 있습니다.
3. 현재 행의 중간 값들은, 바로 위 행의 왼쪽 값 또는 오른쪽 값에서 내려올 수 있습니다.