[c++] 알고리즘 문제 해결 전략 1권 :: 삼각형 위의 최대 경로 (문제 ID: TRIANGLEPATH, 난이도 : 하)

 

https://www.algospot.com/judge/problem/read/TRIANGLEPATH

문제

6
1  2
3  7  4
9  4  1  7
2  7  5  9  4

위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다. 이 때 모든 경로 중 포함된 숫자의 최대 합을 찾는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C(C <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 삼각형의 크기 n(2 <= n <= 100)이 주어지고, 그 후 n줄에는 각 1개~n개의 숫자로 삼각형 각 가로줄에 있는 숫자가 왼쪽부터 주어집니다. 각 숫자는 1 이상 100000 이하의 자연수입니다.

출력

각 테스트 케이스마다 한 줄에 최대 경로의 숫자 합을 출력합니다.

예제 입력

2
5
6
1  2
3  7  4
9  4  1  7
2  7  5  9  4
5
1 
2 4
8 16 8
32 64 32 64
128 256 128 256 128

예제 출력

28
341

나의 답

<생각의 흐름>

완전탐색 => 동적 계획법

 아래로 이동할 때 아래쪽, 오른쪽 대각선 아래 이렇게 2군데로 이동하므로 재귀함수로 구현하여 완전 탐색할 수 있다. 이 때, 완전 탐색의 경우의 수를 세어보면 2^(n+1) 이므로 당연히 시간초과가 된다. 주어진 예제로 따라 써보면 겹치는 구간이 많은데, 중복을 빼면 n(n+1)/2의 재귀만 실행하면 되므로 메모이제이션을 이용하면 O(n^2)의 시간복잡도를 가진다.

<코드>

#include <iostream>
#include <algorithm>

using namespace std;
int n;
int arr[5051];
int memorize[5051]; // 메모이제이션
// 해당 위치에 저장될 수 있는 최대값

int calMaxSum(int row, int idx) { // row : 줄(행), idx : arr에서의 index
    if (memorize[idx] != -1) // 이미 들른 곳이면
        return memorize[idx];
    if (row == n - 1) { // 마지막 줄이면 
        memorize[idx] = arr[idx]; 
        return arr[idx];
    }

    // 마지막 줄이 아니면 아래쪽과 오른쪽 아래에서 오는 값 중 큰 값으로 return
    int tmp1 = arr[idx] + calMaxSum(row + 1, idx + row+1); 
    int tmp2 = arr[idx] + calMaxSum(row + 1, idx + row+2);
    int max = tmp1 > tmp2 ? tmp1 : tmp2;
    memorize[idx] = max;
    return max;
}

int main() {
    int C;
    cin >> C;
    while (C--) {
        cin >> n;
        int index = 0;
        for (int i = 0; i < n; i++) {
            for(int j=0; j<=i; j++){
                cin >> arr[index++];
            }
        }

        fill_n(&memorize[0], 5051, -1); 
        cout << calMaxSum(0, 0)<<endl;
    }
}

그림으로 나타내면 이런 식이다.

 

 두번째 그림에 표시된 것처럼 마지막 줄이 아닌 위치를 조사할 때에는 아래쪽(2)과 오른쪽 아래(7)를 조사해서 존재할 수 있는 더 큰 수를 저장한다. 이런식으로 재귀를 타고 들어가면 마지막 그림의 memorize 배열이 완성되고 가장 첫번째 값이 결과이다.

그림에서는 모양을 저렇게 표현했지만 실제로는 1차원 배열에 값들이 들어가 있고, index값을 조정함으로써 논리적으로 저런 구조를 만들었다.