코드업 2641

이번 글은 코드업 2641번을 풀어보겠습니다.

 

n개의 계단이 있다.
주현이는 계단을 한 번에 1칸 또는 2칸 또는 3칸을 오를 수 있다.
하지만 한번에 3칸을 오르고 나면 힘이 들어 앞으로 두 번은 1칸 또는 2칸만 오를 수 있다.
즉, 한 번에 1칸 혹은 2칸은 조건없이 오를 수 있다. 하지만 3칸을 오르고 나면 적어도 다음 2번의 이동에서는 3 칸을 오르지 못한다. 계단의 수 n이 입력되면 주현이가 이 방법으로 계단을 올라갈 수 있는 서로 다른 방법의 수를 계산하는 프로그램을 작성하시오.

입력
첫 번째 줄에 n이 입력된다.(1 <= n <= 15)

출력
계단을 오를 수 있는 경우의 수를 출력한다.

 

1. 문제분석

음 왜 굳이 3칸을 오르고 나서는 1칸, 2칸만 오를 수 있는 걸까요

흠..... 분석을 해보도록 하죠

 

- n개의 계단을 1, 2, 3칸 씩 오를 수 있다.

- 단, 3칸을 오른 후에는 1, 2칸만 오를 수 있다.

 

계단을 오르면서 3칸을 오르는 경우를 확인할 수 있게 만들어야겠습니다.

 

 

2. 순서도

 

3. 코딩

#include <stdio.h>
int n, cnt=0;
void f(int m, int t){
  if(t!=0) t=0;
  if(n==m) cnt++;
  if(n>m){
    if(t==0) f(m+3, 3);
    f(m+1, t);
    f(m+2, t);
  }
}
int main(){
  scanf("%d", &n);
  f(0,0);
  printf("%d", cnt);
}

처음엔 이렇게 짰는데 오류가 났습니다.

t를 3칸 올라갔는지 확인하기위한 변수로 놓았는데 방법이 잘못 되었나봅니다.

무엇이 문제였을까요......어......

 

t를 한번에 올라간 계단 수로 놓았는데 0이 아닐 때 바로 t=0으로 바꾸어주면 1, 2칸 올랐을 때  경우를 못 하더군요

 

다시 바꾸어 주면

#include <stdio.h>
int n, cnt=0;
void f(int m, int t){
  if(t>0) t--;
  if(n==m) cnt++;
  if(n>m){
    if(t==0) f(m+3, 3);
    f(m+1, t);
    f(m+2, t);
  }
}
int main(){
  scanf("%d", &n);
  f(0,0);
  printf("%d", cnt);
}

 t>0 일 때 -1을  해주면서 실행되도록 해보았습니다.

문제를 풀어보았는데

오 성공했군요

경우를 어떻게 나누어서 코딩해야 할까 고민을 많이 했던거 같습니다.

 

설명을 해보자면

n은 계단 수, cnt는 카운트를 위해 전역변수로 선언했습니다.

계단을 오르기 전 초기값을 함수 f에 전달했고

함수 f에서 매개변수 m은 올라간 총 계단 수, t는 한 번에 올라간 계단 수로 두었습니다.

n==m 일 때는 경우가 1이겠죠.

n>m 일 때를 생각해보면

t=0, 그러니까 전에 3칸을 오르지 않았을 때는 3칸을 오를 수 있고

그렇지 않을 때에는 1칸 오르기 / 2칸 오르기를 할 수 있습니다.

재귀를 통해 와ㄹ랄락 돌려주었습니다.

 

요즘 재귀함수를 이용한 문제를 많이 풀어보고 있는데 아직 좀 어려운 것 같습니다.

연습을 많이 해서 더 익숙해져야겠다는 생각이 들었습니다.