[알고리즘] DP - 계단 오르기(cpp)

N단의 계단이 있고, 한번에 계단을 한 단 또는 두 단을 올라갈 수 있다고 하자. 
최대 두 군데의 계단에는 장애물이 있어서 올라갈 수 없다. 
이 때 N단까지 올라가는 서로 다른 방법의 수를 구하는 프로그램을 작성하시오. 

입력 
표준입력으로 세 정수 N A B가 주어진다. N은 계단의 단수로, 1 이상 30 이하이다. 
A와 B는 장애물이 있는 계단의 위치이다. A와 B는 0 이상 N 이하인 수이며, A와 B가 같을 수 있다. 
A, B 값이 0이라면, 이는 장애물이 없다는 뜻이다. 예를 들어 N, A, B가 3, 0, 1이라고 주어지면 
총 3단의 계단이 있고, 장애물은 1단에만 있다. 조금 더 생각해보면 N, A, B가 3, 1, 0으로 주어져도
같다는 것을 알 수 있다. 

출력
표준출력으로 하나의 정수를 출력한다. N단까지 오는 서로 다른 방법의 수이다. 

힌트 
만약 1단, 2단을 올라갈 수 있다면, 1단에 올라가는 방법은 한 가지, 2단에 올라가는 방법은 두 가지이다. 

예제 입력 1
3 0 1
예제 출력 1
1

---

 

알고리즘 수업 두 번째 과제는 DP를 이용한 미션이었다!

흔히 팩토리얼 계산으로 배우게 되는 dp는 dynamic programming의 약자로, 

현재의 값을 계산하기 위해 이전에 저장해놨던 값을 불러오는 것이 특징이다.

 

아래는 만점 받은 내 코드이다 🔥

 

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

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int cnt=0;
    int n, a, b;
    cin >> n >> a >> b;

    vector<int> stair(n+1);
    stair[0] = 0;
    stair[1] = 1; // 1층
    stair[2] = 2;

    if((a == 1 && b == 2) || (a == 2 && b == 1)){
        stair[1] = 0;
        stair[2] = 0;
    } else if(a == 1 || b == 1){
        stair[1] = 0;
        stair[2] = 1;
    } else if(a == 2 || b == 2){
        stair[1] = 1;
        stair[2] = 0;
    }

    for(int i=3; i<=n; ++i){
        if(i==a || i==b) {
            stair[i] = 0;
            continue;
        }
        stair[i] = stair[i - 1] + stair[i - 2];
    }

    cout << stair[n];
    return 0;
}

 

 

백준에도 비슷한 문제가 있으니 그것도 풀어보면 좋을 것 같다.

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

2579번: 계단 오르기