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

다이나믹 프로그래밍 문제입니다.

 

피라미드모양에 각각 값들이 들어가있습니다.

위에서부터 왼쪽이나 오른쪽을 통해 내려올 때

합이 최대가 되는 경로의 값을 찾는 문제입니다.

 

경우의 수는

 

1. 위치가 가장자리일 때

2. 위치가 중앙일 때

 

2가지가 있습니다.

 

1번의 경우 바로 위의 값을 더해서 DP에 넣어주고

2번의 경우 바로 위의 값이 더할 수 있는 두개의 수를 비교해서 큰값을 더해서 DP에 저장합니다.

 

#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char *argv[])
{
    int n;
    int value = 0;
    int arr[510][510];
    cin >> n;
    for(int i=0; i<n; ++i){
        for(int j=0; j<=i; ++j){
            cin >> arr[i][j];
        }
    }
    for(int i=1; i<n; ++i){
        for(int j=0; j<=i; ++j){
            if(j==0){
                arr[i][j] += arr[i-1][j];
            }
            else if(j==i){
                arr[i][j] += arr[i-1][j-1];
            }
            else{
                arr[i][j] += max(arr[i-1][j], arr[i-1][j-1]);
            }
        }
    }
    for(int i=0; i<n; ++i){
        if(value < arr[n-1][i]){
            value = arr[n-1][i];
        }
    } 
    cout << value;
    return 0;
}