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

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

1932번: 정수 삼각형

한 숫자를 정했을 때 그 위의 두 경로 중 가장 최대값을 정하는 문제이다. 양 끝에 위치하는 숫자일 경우 바로 위 하나의 경로만 더하고 나머지 경우는 dp로 저장한 두 최대 경로 중 더 큰 값을 저장한다.

#include <iostream>
#include <vector>
#define MAX 501
using namespace std;

vector<int> v[MAX];
int dp[MAX][MAX];
int n, tmp, ans;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            cin >> tmp;
            v[i].push_back(tmp);
        }
    }

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

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

    cout << ans << "\n";
    return 0;
}

#include <iostream>
#include <vector>
#define MAX 501
using namespace std;

vector<int> v[MAX];
int dp[MAX][MAX];
int n, tmp, ans;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            cin >> tmp;
            v[i].push_back(tmp);
        }
    }

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

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

    cout << ans << "\n";
    return 0;
}