2579

백준 2579번

Link: 2579번: 계단 오르기

---

문제 설명

오늘도 DP문제다.

그리고 오늘도 내힘으로 푸는데 실패.

앞선 두문제와 비슷하면서도 달랐는데, 이번 문제를 풀수 있느냐 없느냐는 문제를 보고 조건을 이해하여 점화식을 세울 수 있는지였다.

물론 나는 점화식 못세워서 예전 코드 보고, 검색해서 그제서야 이해해서 풀었다.

점화식 세우는 방법은 우선 DP배열의 3번째까지 채우는 방법과 동일했다.

그전에 이 문제에서 DP 배열의 의미를 이해할 필요가 있었다.

DP[N]이란 N번째 계단을 밟았음을 의미한다.

이렇게 이해하고 시작해보면 DP[1]은 첫번째 계단을 밟은것이므로 score[1]이 된다.

DP[2]는 첫번째 계단, 두번째 계단을 둘 다 밟았을때와 두번째 계단만 밟았을때의 점수를 비교하여 큰 값이 곧 DP[2]의 값이 된다.

DP[3]은 조건에 의해 세 계단을 연속으로 밟을 수 없고, 한번에 최대 2개의 계단만 오를 수 있으므로 첫번째 계단과 세번째 계단을 밟았을 때, 두번째 계단과 세번째 계단을 밟았을때의 점수를 비교하여 큰 값이 DP[3]이 된다.

DP[4]를 생각해보자. DP[4]는 첫번째 계단, 세번째 계단, 네번째 계단의 점수를 더한 값과 첫번째 계단, 두번째 계단, 네번째 계단의 점수를 더한 값을 비교하여 더 큰 값이 DP[4]이다.

이는 곧 DP[1] + score[3] + score[4], DP[2] + score[4]를 비교하는 것과 같다.

이를 토대로 점화식을 세워 보면, DP[N] = max(DP[N-3] + score[N-1] + score[N], DP[N-2] + score[N])이라는 점화식을 얻을 수 있다.

이 점화식대로 풀면 풀리는 문제다.

항상 느끼는건데 점화식 세우는게 정말 너무 어렵다. 규칙은 나름대로 찾은것 같지만 뭔가 나사 하나씩은 꼭 빠져있다는 생각이 든다.

푸는방법 까먹을때쯤 한번 더 풀어봐야 할 문제인것 같다.

---

정답 코드

//
// Created by Keith_Lee on 04/01/2019.
//

#include <iostream>

using namespace std;

int N;

int max(int a, int b){
    return (a > b) ? a : b;
}

int main(){
    cin >> N;

    int DP[N+1];
    int score[N+1];

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

    DP[1] = score[1];
    DP[2] = max(score[1] + score[2], score[2]);
    DP[3] = max(score[1] + score[3], score[2] + score[3]);

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

    cout << DP[N] << '\n';

    return 0;
}

---