[BAE/<JOON> 문제풀이] 1932. 정수 삼각형 (DP.007)

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

이런 종류의 트래킹 문제는 확실히 DP가 좋은 해결법이다. 이거 백트래킹하면 100개 사이즈 정도만 되도 시간 초과가 발생할 것이다. 

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<vector<long>> arr;
    vector<vector<long>> dpcnt;
    int n;
    cin >> n;
    arr.resize(n + 1);    
    dpcnt.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        arr[i].resize(i + 1);
        dpcnt[i].resize(i + 1);
        for (int j = 1; j <= i; j++) {
            cin >> arr[i][j];
            dpcnt[i][j] = -1;
        }
    }    

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

    for (int i = n - 1; i >= 1; i--) {
        for (int j = 1; j <= i; j++) {
            int s1 = dpcnt[i + 1][j] + arr[i][j];
            int s2 = dpcnt[i + 1][j + 1] + arr[i][j];
            int s = (s1 > s2 ? s1 : s2);
            if (dpcnt[i][j] < s) dpcnt[i][j] = s;
        }
    }

    cout << dpcnt[1][1] << endl;
    /*for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n-i; j++) {
            cout << " ";
        }
        for (int j = 1; j <= i; j++) {
            cout << dpcnt[i][j] << " ";
        }
        cout << endl;
    }*/
    return 0;
}