# 백준 : 계단 오르기(2579)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_2579_stairs)

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

int main(void) {
    // insert code here...
    int testcase = 0;
    int num = 0;
    int count[301];
    vector <int> stair;
    
    cin>>testcase;
    for(int i=0; i<testcase; i++){
        cin>>num;
        stair.push_back(num);
    }
    
    count[0] = stair[0];
    count[1] = stair[0] + stair[1]; 
    //max(stair[0] + stair[1], stair[1]);
    count[2] = max(stair[0] + stair[2], stair[1] + stair[2]);
    
    for(int i=3; i<testcase; i++) {
        count[i] = stair[i] + max(count[i-2],count[i-3]+stair[i-1]);
    }
    cout<<count[testcase-1]<<endl;
    return 0;
}

풀이

DP는 풀어도 풀어도 쉽지 않구나.
그래도 생각하는 방법이 점점 늘어나는 것 같아서 기분이 좋다.
어떻게 접근해야 하는지는 알았는데, 예외조건에서 생각이 더 진행되지는 못했다.
한번에 3칸을 연속으로 밟을 수 없다는 예외가 왜 이리도 마음에 걸리던지..

방법은 이렇게 풀었다.
i번째 계단에 오르는 조건은
1. i-2번째 계단을 오르고 나서 i번째 계단에 오르는 경우
2. i-3번째 계단을 오르고 나서 i-1번째 계단에 오르고, 그 다음에 i번째 계단에 오르는 경우

결국 1번에서는 i-2번째 계단까지의 총 누적 횟수에 i번째 계단 숫자를 더하면 되고
2번에서는 i-3번째 계단까지의 총 누적 횟수에 i-1번째 계단과 i번째 계단 숫자를 더하면 된다.

DP는 식이 어려운건 아닌데, 그걸 생각해 내는 과정이 힘든 것 같다.
좀 더 분발하자.