[코드트리 챌린지] 3주차 DP l - subproblem을 그대로 합치면 되는 DP / 계단 오르기

https://www.codetree.ai/missions/2/problems/climbing-stairs/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드:

#include <bits/stdc++.h>
using namespace std;

int n;
int dp[1005];

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 1;

    for (int i = 4; i <= 1000; i++) {
        dp[i] = (dp[i - 2] + dp[i - 3]) % 10007;
    }

    cout << dp[n];
}

n층의 계단을 오를 수 있는 방법을 생각해봅시다.

우리가 한 번에 계단을 오를 수 있는 방법은 2칸,3칸씩 두 가지 방법이므로
(n-2 층의 계단을 오를 수 있는 방법) + (n-3 층의 계단을 오를 수 있는 방법) 을 계산하여
n층의 계단을 오를 수 있는 방법을 구할 수 있습니다.

ex) n이 4라고 하면 (2층 계단을 오를 수 있는 방법) + (1층 계단을 오를 수 있는 방법)
= 1 + 0 = 1 로 구할 수 있습니다. 실제로 4층 높이 계단을 도달할 수 있는 방법은 
2칸(2층 계단을 오를 수 있는 방법) + 2칸, 즉 1가지 방법밖에 존재하지 않습니다.