백준) 2579 계단 오르기

계단 오르기

https://www.acmicpc.net/problem/2579

계단을 오르면 점수를 얻는다. 도착지점 까지 일련의 규칙으로 올라갈 때, 얻을 수 있는 최고점은 얼마일까?

도착지점에서 생각해보면, 이 지점에 오기 위해서는 두 계단 밑이나, 한 계단 밑에서 올라왔을 것이다.

또한 그 지점 자체의 최고점이 존재할 것이며, 그 최고점은 두 계단 밑이나 한 계단 밑에서 올라오면서 형성된다.

따라서 각 층마다 상태를 dp로 저장해서 풀면 되겠다.

유의할 점은 한계단씩 연속으로 두번 오를 수 없다는 점이다.

즉 한번 한 계단만 올랐으면, 다음엔 반드시 두 계단을 올라야 한다.

그러면 한 층에서 상태는 두가지로 나눠지고 O(n * 2) 안에 풀 수 있다.

함수 func(int floor, int cnt) = floor층이고, 한 계단씩 연속해서 cnt번 올라왔을 때 얻는 최고점수를 계산해줌.

다음 층으로 오를 때는 cnt = 1이라면 2층 오르는 상태로 이어지며,

cnt = 0 이라면 한 계단 오르거나 두 계단 오르는 상태로 분기된다.

#include <stdio.h>
#include <algorithm>
using namespace std;
 
 
#define M -987654321
 
 
int n;
int stair[301], dp[301][3];
 
 
int func(int floor, int cnt) {
    if (floor > n)
        return M;
 
    if (floor == n)
        return stair[n];
 
    int& ref = dp[floor][cnt];
    if (ref != -1)
        return ref;
 
    if (cnt == 0) {
        int a = func(floor + 1, 1) + stair[floor];
        int b = func(floor + 2, 0) + stair[floor];
 
        return ref = max(a, b);
    }
    else if(cnt==1)
        return ref = func(floor + 2, 0) + stair[floor];
}
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &stair[i]);
        for (int j = 0; j < 3; ++j)
            dp[i][j] = -1;
    }
 
    printf("%d", max(func(1, 0), func(2, 0)));
 
    return 0;
}