[ 백준 2579 - 계단 오르기 ]

### 문제 분석

1. DP
2. 문제 조건을 정확하게 파악해야 풀 수 있는 문제

시간 복잡도

구현

테이블 정의

D[i][j] == 현재까지 j개의 계단을 연속해서 밟고 i번째 계단까지 올라섰을 때 점수 합의 최대값. 단, i번째 계단은 반드시 밟아야 한다.

점화식 정의

D[K][1] == K번째 계단까지 연속해서 1개의 계단을 밟고 올라갔을 때의 비용의 최대값

>> D[K][1] = max(D[k-2][1], D[k-2][2]) + cost[k]

D[K][2] == K번쨰 계단까지 연속해서 2개의 계단을 밟고 올라갔을 때의 비용의 최대값

>> D[k][2] = D[k-1][1] + cost[k]

주의!! >> D[k][2] != max(D[k-1][1], D[k-1][2]) + cost[k]

D[k-1][2] 를 포함해 버리면 연속해서 3개의 계단을 밟는 경우가 포함 될 수 있다. 

초기값의 정의

D[1][1] = cost[1]
D[1][2] = 0
D[2][1] = cost[2]
D[2][2] = cost[1] + cost[2]

헤맸던 부분

만약 이 문제가 DP인 것을 몰랐다면 DP라고 생각하지도 못했을 것 같다.
DP임을 알고 문제에 접근 했어도 결국 테이블 정의, 점화식 도출을 아예 하지 못했다.

얻은 것

DP 유형 학습

전체 코드 [ 내 코드 ]

#include <iostream>
using namespace std;

int board[302][3]; // 1-indexed
int score[302]; // 1-indxed

void init(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}

int N;

void get_input(){
    cin >> N;
    for(int i = 1 ; i <= N; i++)
        cin >> score[i];
}

void print_input(){
    for(int i = 1 ; i <= N; i++)
        cout << score[i];
}

int main(void){
    init();
    get_input();

    board[1][1] = score[1];
    board[1][2] = 0;
    board[2][1] = score[2];
    board[2][2] = score[1] + score[2];

    for(int i = 3; i <= N; i++){
        board[i][1] = max(board[i-2][1] , board[i-2][2]) + score[i];
        board[i][2] = board[i-1][1] + score[i];
    }

    cout << max(board[N][1], board[N][2]) << "\n";
    return 0;
}

느낀점

1. 테이블 정의
2. 점화식 유도
3. 초기값 설정

3가지의 과정을 걸쳐서 문제를 풀이 한다는 것을 알고 있다고 해도 실제로 문제를 풀이 하는 것은 경험적인 측면이 많이 필요한 것 같다. 결국엔 많은 문제를 풀이하는 것 밖에는 답이 없는것 같다.

참조

바킹독님의 유튜브 강의

유튜브 강의 영상
정리를 상당히 깔끔하게 잘 해놓으셔서 이해하기 쉽게 되어있다.