[알고리즘] 백준 1932 - 정수 삼각형

1. 문제

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

2. 입/출력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

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

3. 풀이

4. 코드

using namespace std;
int n;

int dp[500][500];


int main()
{
    cin.tie(0);
    cout.tie(0);
    cin.sync_with_stdio(0);


    cin >> n;

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


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

    int maxN = 0;
    for (int i = 0; i < n; i++) {
        maxN = max(dp[n - 1][i], maxN);
    }

    cout << maxN;


}