[백준] 1932번 정수 삼각형

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

문제

입출력

문제 접근

DP문제이다.
문제 자체는 어렵지 않은데, 어떻게 입력을 받을지 고민을 했었다. 이중 for문을 돌려서 각층마다 나눠서 받도록 진행했고, 최대 숫자를 구할땐, 바로 아래또는 대각선 윗층에서 어느쪽으로 가면 더 큰지에 대해 dp를 통해 구해서 점화식을 만들었다.

코드 구현(c++)

#include <iostream>
#include <cstring>

using namespace std;
int N;
int cache[501][501];
int triangle[501][501];
int dp(int i, int j){
    if(i == N) return triangle[i][j];
    int& res = cache[i][j];
    if(res != -1) return res;
    res = max(dp(i+1,j), dp(i+1,j+1)) + triangle[i][j];
    return res;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cin >> N;
    for(int i = 1 ; i <= N ; i++){
        for(int j = 1 ; j <= i ; j++){
            cin >> triangle[i][j];
        }
    }
    memset(cache, -1 ,sizeof(cache));
    cout << dp(1,1) << "\n";
}