[백준 1932] 숫자 삼각형

[백준 1932] 숫자 삼각형

문제 출처 : https://www.acmicpc.net/problem/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

• 문제 이해하기

트리 형식의 삼각형 구조에서, 맨 위부터 아래로 내려오며 선택되는 숫자의 합이 가장 큰 경로를 찾는 문제다. 현재 예시로 주어진 삼각형의 크기는 5이고, 최대 경로는 7-3-8-7-5로 값이 30이 나오게 된다. 삼각형의 크기를 500까지 줄 수 있어야 하며, 입력 첫째 줄에 삼각형의 크기를 입력하고 두번째 줄부터는 삼각형의 크기만큼, 삼각형안의 숫자를 채웠을 때 출력값으로 최대 경로를 나오게 만들면 되는 문제다.

• 계획 및 문제 해결

내가 정한 삼각형의 크기만큼, 입력 값을 줄 수 있도록 만드는 것이 우선이다. 크기가 500인 삼각형까지 만들기 위해선, 1차원 배열로 하기에는 너무나 크다고 생각했다. 왜냐하면 크기가 3인 삼각형을 만들기 위해선, 총 6개의 배열이 필요할 것이다.

    1
  2   3
4   5   6

따라서 크기가 500인 삼각형은 1~500까지 모두 합한 배열이 필요한데, 물론 가능은 하겠지만 2차원 배열로 나타내면 이후에 경로를 찾을 때도 더 편리할 것 같다는 생각이 들었다.

그래서 500까지의 삼각형을 모두 소화할 수 있도록 501의 크기를 가진 2차원 배열을 생성했다.

int tri[501][501];

위에 예시로 작성한 크기가 3인 삼각형에서, 맨 위의 숫자인 1은 (0,0)에 해당하고, 2와 3은 (1,0) (1,1)로 나타낼 수 있게 되었다. 처음에 설정할 크기에 대한 num값을 입력할 수 있도록 선언해준다면, 아래와 같이 우선 삼각형의 크기와 내용은 입력할 수 있을 것이다.

 int num;
int tri[501][501];
    
cin >> num;
 
for (int i = 0; i < num; i++) {
    for (int j = 0; j <= i; j++) {
        cin >> tri[i][j];
    }
}

이제 최대 경로를 구해야 되는 것을 생각해보기 위해 다시 백준 문제에 나온 예시 문제로 돌아와보자.

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

경로의 첫 시작은 맨 위 (0,0)에 해당하는 7부터 진행된다. 이제 아래로 내려오기 위해 선택할 수 있는 방법은 3과 8 두 가지다. 만약 여기서 경로가 끝나게 된다면, 당연히 8이 더 크기 때문에 오른쪽으로 내려와 값은 15가 될 것이다. 하지만, 삼각형의 크기가 커지면 커질수록 비교 대상이 점점 늘어나게 된다.

세번째 줄인 8, 1, 0까지 비교하면, 두번째 줄에서 8로 내려왔던 것보다 3으로 내려와 8로 가는 것이 최대 경로가 된다. 따라서 그냥 쉽게 값을 비교할 수는 없는 문제였다. 이 삼각형 구조에서, 가장 큰 최대 경로를 구하기 위해서는 결국 모든 이동 경로를 비교해서 출력해야 된다는 점을 알 수 있었다.

우리는 2차원 배열을 통해서 삼각형이 가진 하나하나의 값을 배열로 저장했다. 이제 이 배열을 통해 트리 구조의 삼각형에서 경로를 찾아가는 규칙을 발견해 비교하는 코드를 작성해야 한다. 규칙을 찾기 위해 삼각형의 크기를 조금씩 늘려가며 알아보자.

        7
      3   8
    8   1   0

위의 예시에서 3번째까지만 자른 모습이다.

내려갈수록 최대 경로의 합을 구하기 위해선, 결국 점점 배열의 값을 더하는 과정을 거쳐야 한다. 따라서 이 값을 저장하기 위한 처음에 설정한 똑같은 크기를 가진 2차원 배열을 만들었다.

int data[501][501];

이제 이 배열에 더한 값을 넣을 건데, 아래처럼 하나하나씩 더해가면 최대 경로를 구하는 데 시각적으로 이해하기 편하다.

      10  15
    8   1   0

맨 위의 7값이 두 경로에 모두 합해져 내려온 상태다. 이런 과정으로 값을 점점 내려보낸다. 왜냐하면 우리는 결국 모든 이동 경로를 조사해야 최대 경로를 알 수 있기 때문이다. 이 과정에서만 일어난 합의 과정을 코드로 나타내면 다음과 같다.

data[0][0] = tri[0][0] // 어차피 (0,0) 값은 합계 배열에서도 일치한다.
 
data[1][0] = data[0][0] + tri[1][0];
data[1][1] = data[0][0] + tri[1][1];

여기까지는 매우 쉽게 보이지만, 이제 크기가 3으로 갈 때부터, 비교 대상이 너무 많아져 나누어야 한다. 우선 진행과정을 이해하기 위해서 크기가 3일 때까지 이렇게 나타내보자.

      10  15
    8   1   0
------------------ // 여기서 경로 합의 진행이 이루어지면?
  
   18  16  15 // 두번째 줄까지 합한 값이, 세번째 줄에 있는 숫자로 내려온 상황이다. 

여기서 하나 더 고려해야될 것이 생겼다. 바로 중간에 있는 (3,2)에 해당하는 배열 때문이다. 끝자리에 있는 수 들은, 받아올 값이 (n-1,0)과 (n-1,n-1)의 값으로 정해져 있지만 중간에 있는 수는 받아올 수 있는 값이 2가지의 경우가 있다. 따라서 이 값 중에 더 큰 걸 비교해서 가져와야만 한다.

즉 세번째 줄의 (3,2)에 해당하는 1은 10과 15 중 큰 수를 더해야 하는 것이다. 이는 STL 중에서 알고리즘의 max를 활용해서 가져올 수 있을 거라는 생각이 들었다.

따라서, 왼쪽 끝에 위치한 값 / 오른쪽 끝에 위치한 값 / 비교가 필요한 중간에 위치한 값 이렇게 3가지 경우로 나누어 합계를 저장해 나갈 수 있을 것이다.

for (int i = 1; i < num; i++) {
    for (int j = 0; j <= i; j++) {
        if (j == 0) { // 맨 왼쪽 숫자
            data[i][j] = data[i - 1][j] + tri[i][j];
        }
        else if (i == j) { // 맨 오른쪽 숫자
            data[i][j] = data[i - 1][j - 1] + tri[i][j];
        }
        else { // 비교가 필요한 가운데 숫자
            data[i][j] = max(data[i - 1][j - 1] + tri[i][j], data[i - 1][j] + tri[i][j]);
        }
    }
}

이 과정을 마지막 줄까지 거치게 되면, data 배열에서 맨 마지막에 저장된 값들로만 비교하면 된다.

이 문제는 이동 경로를 표시하라는 게 아니라, 결국 최대 값으로 어떤 값이 나왔냐만 출력하면 되기 때문이다.

따라서, 크기가 5였던 예시 문제는 tri[0][0] ~ tri[4][4]까지 배열이 만들어졌었고, 합계를 저장한 data[4][0] ~ data[4][4] 이 5개의 배열의 크기만 비교해서 출력하면 끝나는 것이다.

결국 삼각형 크기가 n일 때, 2차원 배열에서 앞자리는 n-1이 되고 뒷자리는 0~n-1만큼 이다.

출력 값으로 int형 변수 maxSum을 하나 생성해주고

반목문을 통해 data[n-1][i]로, i값을 증가해나가며 가장 큰 값을 maxSum에 넣으면 된다.

코드로 정리하면 다음과 같다.

int maxSum = 0;
    for (int i = 0; i < num; i++) {
        if (data[num - 1][i] >= maxSum)
            maxSum = data[num - 1][i];
    }
 
    cout << maxSum;

이렇게 진행하면, 최대 이동 경로의 값을 구할 수 있게 된다.

• 전체 소스 코드

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int num;
int tri[501][501];
 
int main() {
 
    int data[501][501];
 
    cin >> num; // 삼각형의 크기 입력
 
    for (int i = 0; i < num; i++) {
        for (int j = 0; j <= i; j++) {
            cin >> tri[i][j];
        }
    }
    
    data[0][0] = tri[0][0];
 
    for (int i = 1; i < num; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0) { // 맨 왼쪽 숫자
                data[i][j] = data[i - 1][j] + tri[i][j];
            }
            else if (i == j) { // 맨 오른쪽 숫자
                data[i][j] = data[i - 1][j - 1] + tri[i][j];
            }
            else { // 비교가 필요한 가운데 숫자
                data[i][j] = max(data[i - 1][j - 1] + tri[i][j], data[i - 1][j] + tri[i][j]);
            }
        }
    }
 
 
    int maxSum = 0;
    for (int i = 0; i < num; i++) {
        if (data[num - 1][i] >= maxSum)
            maxSum = data[num - 1][i];
    }
 
    cout << maxSum;
 
    return 0;
 
}