문제링크 : https://www.acmicpc.net/problem/2579
climeStairs(n) = max(climeStairs(n-1), climeStairs(n-2)) + a[n]
#include<bits/stdc++.h>
using namespace std;
int N;
int a[301];
// 내 풀이에선 2D array로 메모이제이션을 한것이 중요하다.
int cache[3][301];
// n은 순서, c는 이전에 몇 계단을 거쳤는지
int climStairs(int n, int c){
if(n<=0) return 0;
if(c>=3) return -987654321;
// 여기서 c에 따른 n으로 메모이제이션을 해주는것이 중요하다.
int& ret = cache[c][n];
if(ret != -1) return ret;
// 2칸 점프하였을 때는 c 즉 체크값을 1로주고(이전 계단은 거치지 않았기 때문)
// 1칸 점프하였을 때는 c를 1 더해준다 (이전 계단을 거쳤기 때문에)
ret = max(climStairs(n-1, c+1)+a[n], climStairs(n-2, 1)+a[n]);
return ret;
}
int main(){
ios_base::sync_with_stdio(false);
// freopen("../input.txt","rt",stdin);
memset(a, -1, sizeof(a));
memset(cache, -1, sizeof(cache));
cin >> N;
for(int i=1; i<=N; i++){
cin >> a[i];
}
cout << climStairs(N, 1) << endl;
return 0;
}
메모이제이션을 할때 c를 배제하고 1차원으로 해결하려고하면, cache에는 c와 상관없이 가장 큰값을 저장하기 때문에 문제가 발생한다. 1칸을 지나온 n번째의 값과 2칸을 지나온 n번째의 값은 다른 값이기 때문이다.
2차원 배열을 사용하여 메모이제이션을 한 것, 끝을 반드시 지나야 하기 때문에 끝에서 시작한 아이디어들을 기억하자.