백준 02579 - 계단 오르기

출처 : www.acmicpc.net/problem/2579

 

고려사항

- cnt 는 연속해서 도달했던 층들의 길이이다. 즉 memo[n][2] 는 memo[n-1][1] 에서 한 칸 이동,

memo[n][1] 은 memo[n-2][ ] 층에서 두 칸 이동해서 n 번째 계단에 도달했다는 뜻.

- cnt == 2 인 경우는 memo[n-1][1] + score[n]

- cnt == 1 인 경우는 memo[n-2][1] 와  memo[n-2][2] 중 큰 값 + score[n]

- 기저 사례에 2층도 포함되며 cnt == 2  이라면 1,2 층의 합, cnt == 1 이라면 시작부터 두칸 이동한 경우!

 

 

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

int score[301];
int memo[301][3];

int dp(int num, int cnt){
    int &v = memo[num][cnt];
    if(num == 1){
        v = score[1];
        return v;
    }

    if(num == 2){
        if(cnt == 1){
            v = score[2];
        }else if(cnt == 2){
            v = score[1] + score[2];
        }

        return v;
    }

    if(v != -1){
        return v;
    }

    if(cnt == 1){
        v = max(dp(num-2, 1), dp(num-2, 2)) + score[num];
    }else{
        v = dp(num-1,1) + score[num];
    }

    return v;
}

int main() {
    int n, ans;
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>score[i];
    }

    memset(memo,-1,301*3*4);
    ans = max(dp(n, 1),dp(n, 2));

    cout<<ans;
    return 0;
}