[C++] 백준 BOJ 1932 정수 삼각형

문제 링크 : https://boj.kr/1932

입력이 위 그림과 같이 정삼각형 형태의 피라미드의 형태로 주어진다.

이 형태를 어떻게 입력받아야 할까? 하고 고민을 해봤다.

첫줄부터 인덱스를 메겨서

1

2 3

4 5 6

7 8 9 10

11 12 13 14 15

이런 형태로 각 줄의 첫 인덱스들이 1, 2, 4, 7, 11 이런 식으로 늘어나는 계차수열 형태로 입력받아야 하는가? 하고 고민도 해봤다.

하지만 입력을 보니 그냥 이런 형태 그대로 입력 받아도 계산하는데는 문제 없겠구나 싶었다.

따라서, N*N 형태의 일반 매트릭스 형태로 입력받고 모든 노드를 0으로 초기화 시킨 상태에서 계산하도록 하였다.

이 문제는 재귀로 풀게되면 엄청난 연산 횟수로 시간초과를 발생시킬 수 있는 문제이다.

상위 단계에 있는 인접 노드의 값을 여태까지의 누적 합으로 저장하고 그 값 중에서 최대값 찾아서 계산하면 된다.

그리고 상위 노드의 누적 합들은 하위 노드에서 그 이전의 연산 값들을 그대로 활용할 수 있는 것을 찾아냈다.

따라서 이 문제는 동적 계획법을 이용하여 하위 노드에서 연산시 상위 노드의 좌측, 우측 중에서 가장 높은 누적 값을 선택해서 누적해 나가면 풀 수 있게 된다.

반복되는 연산을 매 횟수마다 실행할 필요 없이 미리 계산해 둔 값을 이용하는 것이다.

4번째 줄에 있는 arr[4][2]를 기준으로 arr[3][1] 또는 arr[3][2]의 부모 노드 중에서 누적 최대합이 큰 것을 찾으면 된다.

또한, 이 연산은 부모 노드만 검사하면 되기 때문에 입력과 동시에 연산을 처리할 수 있다.

예제 테스트케이스를 직접 돌려보았다. 

arr[4][2]의 값을 구하려면 arr[3][1]과 arr[3][2]의 누적 합 중에서 큰 것을 택해서 현재 입력과 더하면 되는 것이다.

따라서, 둘 중에서 큰 값인 18을 선택하고 자기 자신의 값인 7을 더해서 25가 되었다.

식으로 정리하면 arr[i][j] = arr[i][j] + max(arr[i-1][j-1], arr[i-1][j]) 가 되겠다.

다만, 여기서 arr[4][1]의 경우를 살펴본다면 상위 노드의 좌측 값은 존재하지 않게되는 문제가 발생한다. 하지만 모든 배열을 이미 0으로 초기화하고 시작했으므로 [4][1]의 좌측 상위 노드인 [3][0]은 0이고 [3][1]은 18이기 때문에 어짜피 큰 값인 18을 선택하게 되므로 문제가 되지는 않는다.

// BOJ 1932 정수 삼각형
#include <bits/stdc++.h>
 
using namespace std;
 
int max(int a, int b){
    return a > b ? a : b;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("../input.txt", "r", stdin);
 
    int N, result = 0;
    cin >> N;
    vector<vector<int> > arr(N+1, vector<int>(N+1, 0));
 
    for(int i = 1; i <= N; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> arr[i][j];
            // 자신의 좌측, 우측 부모 노드 중 큰 값을 더해서 누적
            arr[i][j] += max(arr[i-1][j-1], arr[i-1][j]);
            if(i == N) // 마지막 줄에서 최대값 계산
                result = max(result, arr[i][j]);
        }
    }
    cout << result;
 
    return 0;
}