9. codeup 2641 : 숏다리의 계단 오르기 (Small) 문제 해결

 

이전 게시글과 비슷한 느낌의 문제를 하나 풀어보겠습니다.

출처 <코드업 사이트>

계단을 오르는 경우의 수를 계산하는 문제인데요. 1칸, 2칸, 3칸씩 오를 수 있지만 3칸을 오른뒤에 두번은 1칸 또는 2칸 밖에 오르지 못하는 조건이 붙어있네요. 

 

이번 문제도 재귀함수를 이용하여 풀면 좋을 것 같다고 생각하였습니다. 우선 올라가야할 계단의 수를 입력 받고 올라간 계단의 수와 3칸 올라가는 것에 대한 조건을 판별해줄 변수를 인자로 갖는 함수를 만들어 줍니다. 3칸씩 올라가는 경우의 수를 우선적으로 세줍니다. 그러나 3칸을 갈때에는 조건이 있으므로 m인자에 3이라는 값을 줍니다. 그럼 다음 함수 호출부터 m의 값을 1씩 줄이게 될텐데 m의 값이 0보다 클때 3칸을 가지 못하도록 하여 이 조건을 만족시킬 수 있습니다. 3칸씩 올라가고 올라가야할 계단의 수를 넘었다면 이전 재귀로 복귀하여 2칸을 오르게 됩니다. 이런 반복 작업이 계속되다가 올라가야할 계단의 수와 오른 계단의 수가 같아지면 (b와 n 의 값) 경우의 수를 저장하는 변수의 값이 1증가하게 됩니다. 이러한 알고리즘을 코드로 구현하였습니다.

#include <stdio.h>

int a,b;  //경우의수, 오를 계단의 수

void f(int n,int m){   //n:오른 계단의 수, m: 3칸씩 오른 후 조건
    if(m>0) m--;   //3칸씩 오른 후 다시 3칸을 오를 수 있도록 카운트
    if(b==n) a++;  //오를 계단의 수와 오른 계단의 수가 같아지면 경우의수 +1
    else if(b>n){ //오를 계단 수보다 오른 계단 수가 적어야 함
        if(m==0) f(n+3,3);  //3칸 이동
        f(n+2,m); //2칸 이동
        f(n+1,m); //1칸 이동
    }
}


int main(){
scanf("%d",&b);  //오를 계단 수 입력
f(0,0);   //함수 호출
printf("%d",a);  //경우의 수 출력



}

앞선 문제와 같이 재귀함수를 활용하여 계단을 오르고 , 계단 수가 맞지 않다면 이전 재귀로 복귀하고, 계단 수가 맞다면 출력값을 1증가시키는 과정을 이용하여 문제를 해결할 수 있었습니다.

 

예를 들어 b가 5이면 

3 2

3 1 1

2 3

2 2 1

2 1 2

2 1 1 1 

1 3 1

1 2 2

1 2 1 1 

1 1 3

1 1 2 1

1 1 1 2

1 1 1 1 1

 

총 13개가 있겠네요

 

이번 글은 여기까지 입니다! 읽어주셔서 감사합니다.