[BOJ / C++] 정수 삼각형 (다이나믹 프로그래밍)

문제링크: https://www.acmicpc.net/problem/1932

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n;
    cin >> n;
    vector<vector<int>> board(n+1, vector<int>(n+1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> board[i][j];
        }
    }

    vector<vector<int>> d(n+1, vector<int>(n+1, 0));
    d[1][1] = board[1][1];
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            d[i][j] = board[i][j] + max(d[i-1][j], d[i-1][j-1]); 
        }
    }

    cout << *max_element(d[n].begin(), d[n].end());
}

 

 

2. 분석

1. dp 테이블:

d[i][j]: 해당 경로까지 왔을 때 최댓값

 

2. 점화식:

d[i][j] = board[i][j] + max(d[i-1][j], d[i-1][j-1]);

0행과 0열이 0으로 초기화되어있기 때문에 OOB 예외처리를 하지 않아도 된다.

 

 

3. 시간복잡도

dp테이블을 채우는데 n^2이 든다. O(n^2)인데 n = 500이므로 n^2 = 250,000 < 10^8 이므로 시간제한 2초내에 통과 가능하다.