징검다리를 건너는 경우의 수 구하기

A] [징검다리 0] [징검다리 1] ... [징검다리 N-1] [B

철수는 다리가 짧아 징검다리를 한번에 한칸, 혹은 두칸만 건널 수 있다.
징검다리가 N개 있을때의 철수가 A에서 B로 이동할수 있는 경로의 수를 모두 구하라.

(아래 추가조건은 풀어도 되고, 안풀어도 되는 문제)
추가 조건1: '징검다리 p'는 너무 미끄러워 밟을 수 없다.
추가 조건2: 영희는 다리가 길어 징검다리를 한번에 한칸, 두칸, 혹은 세칸 건널 수 있다.

예(기본 문제 기준):

N == 0
A] [B
path 1: A -> B

N == 1
A] [징검다리 0] [B
path 1: A -> 0 -> B
path 2: A -> B

N == 2
A] [징검다리 0] [징검다리 1] [B
path 1: A -> 0 -> 1 -> B
path 2: A -> 1 -> B
path 3: A -> 0 -> B

예(추가조건 1기준):

N == 3, p == 2
A] [징검다리 0] [징검다리 1] [징검다리 2] [B
path 1: A -> 0 -> 1 -> B
path 2: A -> 1 -> B

징검다리 2가 미끄럽기때문에 2를 밟는 path인 0 -> 2, 1 -> 2, 2 -> B 가 불가능하다.

------------------------

일단 추가조건 없이 푸는 것은 일전에 풀었던 계단 올라가는 경우의 수와 비슷하게 재귀나 DP로 풀 수 있다.

N의 제한조건이 없지만, 가능경로의 수가 int 범위를 넘지 않기 위해서는 N<=30가 적절하다고 나름의 가정을 하겠다.

int steppingStone(int N) {
    if(N < 0) return 0;
    if(N == 0) return 1;
    if(N == 1) return 2;
    
    return steppingStone(N-1) + steppingStone(N-2);
}

테스트 결과 아래와 같다.

답이 없어서 채점도 못해봤다. 추가조건2는 다음에 시간날 때 풀어야겠다.

int main() {
    
    int N;
    int p;
    
    //추가조건 없이
    cin >> N;                            // 20
    cout << steppingStone(N) << endl;    // 17711
    
    // 추가조건1 bruteForce ver
    cin >> N >> p;                        // 20 13
    cout << ss1(N, p) << endl;            // 4901
    
    // 추가조건1 간략화 버전
    cin >> N >> p;                        // 20 13
    cout << addition(N, p) << endl;        // 4901
    return 0;
    
}