백준 1932 정수삼각형

문제

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

풀이전략

1. 문제에서는 대각선 왼쪽과 대각선 오른쪽이라고 말했지만, 결국 배열로 따지면
   예제에서 보이듯이 바로 밑에 값과 오른쪽 아래 값을 찾으면 된다. 이를 배열로 접근하면 더 쉽다.
2. 층을 내려가면서 최대값을 저장한다.
   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을 하는데 지장을 주었다. 이런 실수를 하지 않도록 노력해야겠다.