문제링크: https://www.acmicpc.net/problem/1932
cache[r][c] = max(tri(n, n+1), tri(n+1, n+1)) + a[r][c]
#include<bits/stdc++.h>
using namespace std;
#define mine
int N;
int cache[501][501];
int a[501][501];
int tri(int r, int c){
if(r==N) return a[r][c];
int& ret = cache[r][c];
if(ret != -1) return ret;
// 간단하다. 바로 밑에 값과 대각선 밑에 값중 최대값을 return해주는 것이다.
ret = max(tri(r+1,c)+a[r][c], tri(r+1, c+1)+a[r][c]);
return ret;
}
int main(){
ios_base::sync_with_stdio(false);
// freopen("../input.txt","rt",stdin);
memset(cache, -1, sizeof(cache));
cin >> N;
for(int i=1; i<=N; i++){
for(int j=1; j<=i; j++){
cin >> a[i][j];
}
}
cout << tri(1, 1) << endl;
return 0;
}
이 문제에서는 0이 input으로 들어오는게 크게 의미는 없지만, 나는 풀때 이 존재를 잊고 풀었다. 이를 잊지말아야한다. 또한 이문제를 풀때 int& ret에서 &을 빼먹어 memoization을 하는데 지장을 주었다. 이런 실수를 하지 않도록 노력해야겠다.