백준 2579 계단오르기

문제

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

풀이전략

1. 한번에 1~2계단 씩 밖에 못움직인다.
2. 연속된 세계단을 오르는 것은 불가능하다.
   -> 메모이제이션을 2D로 만들어 조건을 준다.
3. 마지막 도착 계단은 반드시 밟는다.
   -> 마지막에서 재귀를 시작한다.
   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차원 배열을 사용하여 메모이제이션을 한 것, 끝을 반드시 지나야 하기 때문에 끝에서 시작한 아이디어들을 기억하자.