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

www.acmicpc.net/problem/1932

1932번: 정수 삼각형

크게 어렵지 않은 DP 문제입니다. 삼각형에서 가장 왼쪽 혹은 오른쪽은 바로 위 하나의 숫자만 받아 합을 구할 수 있습니다. 그 외 중간에 있는 숫자들은 양쪽 위 두 개의 숫자 중 큰 것을 받아 합을 구하면 됩니다.

#include<iostream>

using namespace std;

#define MAX 501

int DP[MAX][MAX];

int main(void)
{
    int n; cin >> n;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            int temp; cin >> temp;
            if (j == 1) DP[i][j] = temp + DP[i - 1][j];
            else if (j == i) DP[i][j] = temp + DP[i - 1][j - 1];
            else DP[i][j] = temp + max(DP[i - 1][j], DP[i - 1][j - 1]);
        }
    }

    int max = 0;
    for (int i = 1; i <= n; i++) {
        if (DP[n][i] > max) max = DP[n][i];
    }

    cout << max;

    return 0;
}

이후 마지막 층에서 가장 큰 수를 출력하면 됩니다.