[BOJ2579 C++] 계단 오르기

실버 3짜리 문제.
근데 실버 1짜리는 오히려 한번에 쉽게 풀었는데 실버 3이 왜 더 어렵냐 ...

사실 지금까지는 점화식! 이라고 해서 세운 적이 없고,
그냥 이건 이렇게 되겠다 ~ 하고 풀었던 건데....

이번에 풀면서 느꼈는데 DP 풀기 전에는 꼭 점화식 세우고 검증하고 시작해야될 것 같음.

계단 오르기
엄청 쉬워보이는데 조건이 생각보다 까다롭다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.

3. 마지막 도착 계단은 반드시 밟아야 한다.

이런 조건이 있는데 ..

연속된 세 개의 계단
마지막 도착 계단은 반드시 밟는다

이 두개의 조건이 처음 봤던 건지 .. 어떻게 하는지 잘 모르겠더라.

처음 시도했던 방법들은

마지막 도착 게딴은 반드시 밟아야하니까 마지막 도착 계단부터 그냥 시작해서

계단을 내려가는 방법으로도 해봤고..

연속된 세 개의 계단은 지금까지 몇번 밟았는지 확인하는 것을 둬서 체크하면서 가기도 했고.

근데 이렇게 풀면 안되는 걸 풀이를 보고 알았다.

내가 지금까지 소홀히 했던 "점화식" 이라는 것만 잘 세우면 그냥 끝나더라.

마지막 도착 계단을 밟는다는건, 점화식에 Arr[N] 가 무조건 들어가게 되면 될 것 같고,

연속된 세 개의 계단 때문에 조금 생각을 해야된다.

점화식 세워보자 ~ !

N = 1일 경우 (첫 번째 계단)
DP[1] = Arr[1] 무조건이지

N=2일 경우 (두 번째 계단)
DP[2] = Arr[1] + Arr[2] (한번에 2칸으로 뛰는 0 + Arr[2]가 Arr[1] + Arr[2]보다는 무조건 작기 때문에)

N=3일 경우 (세 번째 계단)
한번에 3개의 계단을 착착 밟고 갈 수 없기 때문에 DP[3] = DP[2] + Arr[3]은 불가능하다
DP[3] = MAX(Arr[1] + Arr[3], Arr[2] + Arr[3]) 이겠지

N=4일 경우
여기서부터 생각을 잘해야 N으로 확장이 가능하다
DP[4] = MAX(Arr[1] + Arr[3] + Arr[4], Arr[1] + Arr[2] + Arr[4])
-> MAX(Arr[1] + Arr[3] + Arr[4], DP[2] + Arr[4])

N일 경우는?
DP[N] = MAX(DP[N-3] + Arr[N-1] + Arr[N], DP[N-2] + Arr[N])

이렇게 하면 되드라 . . .

그리고 뭐 크고작고 계산하는건 algorithm library에서 max 쓰면된다. (코드엔 없음 ㅎ)

//
// Created by 신성준 on 2023/03/05.
//

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    int stair[301] = {0,};
    int max_stair[301] = {0,};
    int continue_check[301] = {0,};
    cin >> N;
    for(int i = 1; i <= N; i++){
        cin >> stair[i];
        continue_check[i] = 1;
    }

    for(int i = 1; i <= N; i++){
        if(i == 1){
            max_stair[1] = stair[1];
        }
        else if(i == 2){
            max_stair[2] = stair[1] + stair[2];
        }
        else if(i == 3){
            int up_2 = stair[1] +  stair[3];
            int up_1 = stair[2] + stair[3];

            max_stair[3] = (up_1 > up_2) ? up_1 : up_2;
        }
        else{ // N
            int up_1 = max_stair[i-3] + stair[i-1] + stair[i];
            int up_2 = max_stair[i-2] + stair[i];

            max_stair[i] = (up_1 > up_2) ? up_1 : up_2;
        }
    }

    cout << max_stair[N];
}

흠 .. 생각보다 쉽지 않네 ..