[BOJ / C++] 1946번 : 정수 삼각형

문제

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

출력

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

Solved.ac 레벨

실버 I

풀이

다이나믹 프로그래밍 (DP) 문제였는데 나한테는 조금 어려워 시간이 꽤 걸렸다. 먼저 제출한 코드다.

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    int dp[501][501];
    int arr[501][501];

    cin >> n;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            cin >> arr[i][j];
        }
    }

    dp[1][1] = arr[1][1];

    for(int i = 2; i <= n; i++){
        for(int j = 1; j <= i; j++){
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j];
        }
    }

    int maxSum = 0;
    for(int i = 1; i <= n; i++){
        if(dp[n][i] > maxSum) {
            maxSum = dp[n][i];
        }
    }

    cout << maxSum << "\n";

    return 0;
}

dp 배열은 삼각형의 맨 위에서 아래로 내려가며 각각 왼쪽 대각선, 오른쪽 대각선으로 이동했을 때의 합을 저장한다.

arr 배열은 삼각형을 저장한다. 삼각형의 숫자를 저장할 때는 dp 배열과의 탐색을 용이하기 위해 0번째 인덱스는 생략하고 1부터 받았다.

두 배열 공통으로 i는 삼각형의 높이를, j는 높이가 i인 곳에 존재하는 숫자의 개수다.

 

dp[1][1]에는 맨 위의 숫자를 저장한 뒤 점화식을 반복하여 수행한다.

 

문제 예제의 삼각형을 예를 들었을 때 dp[1][1]은 7이 된다. 

 

i = 2 라면
dp[2][1] = max(dp[1][0], dp[1][1]) + arr[2][1] = max(0, 7) + 3 = 10
dp[2][2] = max(dp[1][1], dp[1][2]) + arr[2][2] = max(7, 0) + 8 = 15

 

위와 같이 반복을 2회 수행하는데, 두 번째 줄에는 3과 8 두 수 밖에 없기 때문이다. 따라서 삼각형의 맨 위인 7에서 왼쪽, 오른쪽으로 갔을 때의 값을 이차원 배열에 각각 저장하게 되고, dp 탐색이 끝난 이후에는 1층에서부터 n층 까지의 합 중 가장 큰 합을 출력하면 된다.

 

1946번: 신입 사원