4. 백준 2579 계단 오르기 문제 공부

1. 문제를 풀면서

 백준 온라인 저지에서 푼 문제를 내 블로그에 다루려고 한다. '동적 계획법 기초 단계'의 네 번째 문제이다. 동적 계획법을 이런 방식으로 사용하는구나 하고 느낄 수 있다. 동적 계획법 기초 단계 9번 문제인 '포도주 시식' 문제와 비슷하다!

2. 문제 출처 및 보기

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

3. 문제 해결

 계단 오르기는 한 번에 한 칸 또는 두 칸 오를 수 있으며 연속으로 두 두 번까지만 오를 수 있다. 예를 들면 한 칸을 1, 두 칸을 2라고 한다면 

(1) 1+1

(2) 1+2

(3) 2+1 

(4) 2+2

이렇게 네 가지 방법이 있는 것이다. 하지만 더 간단하게 생각해볼 수 있다. 

 현재 N번째 계단에 서 있다고 한다면 한 칸 전에서 오는 방법(CASE 1) 두 칸 전에서 오는 방법(CASE 2)이 있다. 계산 법은 다음과 같이 생각해 볼 수 있다.

(CASE 1) 현재 계단(N)에서 얻을 수 있는 최대 점수 = 현재 계단(N) 점수 + 한 칸 전 계단(N-1)에서 얻을 수 있는 최대 점수

(CASE 2) 현재 계단(N)에서 얻을 수 있는 최대 점수 = 현재 계단(N) 점수 + 두 칸 전 계단(N-2)에서 얻을 수 있는 최대 점수

 여기서 하나를 더 생각해야 한다. 문제에 연속 세 칸을 밟을 수는 없다는 조건이 있으므로 '(CASE 1)'을 고쳐줘야 한다. 왜냐하면 '한 칸 전 계단(N-1)에서 얻을 수 있는 최대 점수'를 구하는 과정에서 한 칸 한 칸 이동했었다면 현재 칸까지 합쳐서 연속해서 세 칸을 밟는 것이기 때문이다. 아래는 최종 케이스다.

(CASE 1') 현재 계단(N)에서 얻을 수 있는 최대 점수 

= 현재 계단(N) 점수 + 한 칸 전 계단(N-1)에서 얻을 수 있는 최대 점수 + 세 칸 전 계단(N-3)에서 얻을 수 있는 최대 점수

(CASE 2 ) 현재 계단(N)에서 얻을 수 있는 최대 점수 = 현재 계단(N) 점수 + 두 칸 전 계단(N-2)에서 얻을 수 있는 최대 점수

 

4. 소스코드 

이렇게 네 가지 방법이 있는 것이다. 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int N, score[300]{0}, dp[300]{ 0 };
    
    // 데이터 입력
    scanf("%d", &N);
    for (int idx = 0; idx < N; idx++) {
        scanf("%d", &score[idx]);
    }
    
    // 문제 해결
    for (int idx = 0; idx < N; idx++) {
        int case1 = score[idx], case2 = score[idx];
        if (idx - 1 >= 0) {
            case1 += dp[idx - 2];
            case2 += score[idx - 1];
            if (idx - 3 >= 0)
                case2 += dp[idx - 3];
        }
        dp[idx] = max(case1, case2);
    }
 
    // 결과 출력
    printf("%d\n", dp[N-1]);
    return 0;
}