[백준 1932번] 정수 삼각형 c++

www.acmicpc.net/problem/1932

1932번: 정수 삼각형

내려오면서 그때그때 합이 가장 큰 숫자를 골라서 내려오는 식으로 알고리즘 구성했다

전에 한번 풀어본 유형이라 빠르게 풀었음

 

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
 
int arr[501][501];
int dp[501][501];
int n;
 
int p(int x, int y) {
 
    if (x == n) return 0;
 
    int& ret = dp[x][y];
    if (ret != -1) return ret;
    return ret = arr[x][y] + max(p(x + 1, y), p(x + 1, y + 1));
}
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i + 1; j++)
            cin >> arr[i][j];
    memset(dp, -1, sizeof(dp));
    cout << p(0, 0);
 
    return 0;
}