2641 : 숏다리의 계단 오르기 (Small)

문제

숏다리의 계단 오르기 (Small)

 

코드

#include <iostream>

using namespace std;

int dp[16];
int N,ans;
void dfs(int current,int before_step,int before_before_step){
    if(current==N){
        ans++;
        return;
    }
    else if(current>N) return;
    else{
        if(before_step==3||before_before_step==3){
            dfs(current+1,1,before_step);
            dfs(current+2,2,before_step);
        }
        else{
            dfs(current+1,1,before_step);
            dfs(current+2,2,before_step);
            dfs(current+3,3,before_step);
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N;
    dfs(1,1,0);   //첫 시작을 한칸
    dfs(2,2,0);   //첫 시작을 두칸
    dfs(3,3,0);   //첫 시작을 세칸
    cout<<ans;
    
}

 

풀이

문제만 제목만 보고 당연히 DP인 줄 알았더니, 칸을 오르는 최소 횟수가 아니라 모든 경우의 수라서 백트래킹으로 접근했습니다.

세 칸을 오르면 다음번 이동과 다음 다음 번 이동까지 한번에 세 칸을 오르지 못합니다.

 

채점