정수 삼각형 1932 (백준으로 C++ 공부하기 38일차)

문제

1932번: 정수 삼각형

생각

어제 푼 RGB 거리 1149와 비슷하게 이번에는 최대값을 구하는 것이다.

코드

#include <iostream>
using namespace std;
const int MAXN = 501;

int main() {
    int n; cin >> n;
    int map[MAXN][MAXN];
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= i; j++) {
            cin >> map[i][j];
        }
    }

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

    cout << M;
}