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

출력

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

 

 

DP 문제.

각 층에 있는 숫자들과 이전 층의 왼쪽 또는 오른쪽 대각선의 수를 더해 최대값을 DP 테이블에 저장하면서 내려와야 한다.

 

정수 삼각형을 나타내는 v 벡터 변수와

DP 테이블을 이용하여 최대값을 계산하는 dp 벡터 변수를 이용.

또한 접근이 쉽게 1 ~ N행, 1 ~ N 열로 하여 크기도 N + 1, N + 1 만큼 선언했다.

 

1층의 수는 1개이기 때문에 dp[1][1]에 v[1][1]을 저장하여 시작.

 

i는 층, j는 열을 나타낸다.

 

2층부터 계산을 하면 되는데, 각 층에서 1번 열과 마지막 열은 각각 이전 층의 1번 열과 마지막 열을 더한 값이다.

그렇기 때문에 조건을 걸어두어 계산이 1번만 되도록 하였다.

(j가 1인 경우 또는 j가 i인 경우)

 

그 외 열번호는 현재 층의 수와 이전 층의 왼쪽 대각선 수 or 오른쪽 대각선 수를 더해 최대값을 저장한다.

  점화식

=> dp[i][j] = max(dp[i - 1][j - 1] + v[i][j], dp[i - 1][j] + v[i][j])

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>

using namespace std;

int main(void){
    int N, ans = 0;

    cin >> N;

    vector<vector<int>> v(N + 1, vector<int>(N + 1, 0));
    vector<vector<int>> dp(N + 1, vector<int>(N + 1, INT_MIN));

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

    dp[1][1] = v[1][1];

    for(int i = 2; i <= N; i++){
        for(int j = 1; j <= i; j++){
            if(j == 1){
                dp[i][j] = dp[i - 1][j] + v[i][j];
            }
            else if(j == i){
                dp[i][j] = dp[i - 1][j - 1] + v[i][j];
            }
            else{
                dp[i][j] = max(dp[i - 1][j - 1] + v[i][j], dp[i - 1][j] + v[i][j]);
            }
        }
    }

    for(int i = 1; i <= N; i++){
        ans = max(ans, dp[N][i]);
    }

    cout << ans;
    
    return 0;
}