백준 1932 (정수 삼각형) / C++

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

1932번: 정수 삼각형

> 풀이

dp bottom-up 방식을 사용했습니다.

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

int dp[501][501];
int a[501][501];
int res = -1;

int main(void) {
        int n;

        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
                for (int j = 0; j <= i; j++) 
                        scanf("%d", &a[i][j]);
        }

        dp[0][0] = a[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] + a[i][j];
                        else if (j == i) dp[i][j] = dp[i - 1][j - 1] + a[i][j];
                        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i][j];
                }
        }
        sort(dp[n - 1], dp[n - 1] + n);
        printf("%d", dp[n - 1][n - 1]);
}

(개발 환경 : vs code)