코드업 2833번

이 글에서는 코드업 2833번 문제를 풀이해보겠습니다.

https://codeup.kr/problem.php?id=2833 

[상태 정의를 통한 탐색] 계단 오르기 1-1

---

문제 설명

 

OO이가 계단을 올라가려고 한다.

계단은 모두 n칸으로 구성되어 있다.

OO이는 한 번에 1칸, 2칸, 3칸을 오를 수 있다.

OO이가 k개 이하의 칸을 이용하면서 0번째 칸에서 출발하여 n번째 칸으로 올라가는 서로 다른 방법의 수를 구하는 프로그램을 작성하시오.

만약 n이 3이고, k가 3 이면

- 1 2 : 0번째, 1번째, 3번째 계단을 이용하여 목표에 도달
- 2 1 : 0번째, 2번째, 3번째 계단을 이용하여 목표에 도달
- 3   : 0번째, 3번째 계단을 이용하여 목표에 도달

으로 모두 3가지 경우가 있다.

---

입력

 

첫 번째 줄에 n과 k가 공백을 기준으로 입력된다.

[입력값의 정의역]
[1 ≤ n ≤ 40]
[1 ≤ k ≤ 15]

---

출력

 

계단을 올라가는 서로 다른 경로의 수를 출력한다.

 

문제를 읽어보시면 알겠지만, 코드업 2832번의 단순 변형 문제입니다.

3칸을 올라갈 수 있기 때문에, 이용가능한 칸 수가 1개, 2개, 3개 이상 남았고 계단이 3칸 남았을 때 오를 수 있는 경우의 수들만 추가해주고, n개의 계단을 오르는 방법의 수 = n-1개의 계단을 오르는 방법의 수 + n-2개의 계단을 오르는 방법의 수 + n-3개의 계단을 오르는 방법의 수 라는 식으로 재귀식을 바꾸어 주면 바로 풀 수 있습니다.

그 경우의 수는 각각 1가지 (3칸), 3가지(1칸+2칸, 2칸+1칸, 3칸), 4가지(1칸+2칸, 2칸+1칸, 3칸, 1칸+1칸+1칸) 입니다.

 

알고리즘 순서도를 그리면 아래와 같이 될 것입니다. 보시다시피, 2832번 문제 풀이의 순서도에서 3칸 남았을 경우를 추가해준 것과 재귀식을 바꾸어 준 것 이외에는 달라진 것이 없습니다.

 

순서도까지 작성 했으니, 바로 코드를 짜보죠.

#include <stdio.h>

int k, n;

int f(int m, int cnt)
{
  if(cnt <= 0 && m > 0)
  {
    return 0;
  }
  else
  {
    if(m == 1)
    {
      return 1;
    }
    else if(m == 2)
    {
      if(cnt == 1)
      {
        return 1;
      }
      else
      {
        return 2;
      }
    }
    else if(m == 3)
    {
      if(cnt == 1)
      {
        return 1;
      }
      else if(cnt == 2)
      {
        return 3;
      }
      else
      {
        return 4;
      }
    }
    else
    {
        return f(m-1, cnt-1) + f(m-2, cnt-1) + f(m-3, cnt-1);
    }
  }
}

int main()
{
  scanf("%d %d", &n, &k);
  printf("%d", f(n, k-1));
}

예상대로 정상적인 결과를 내놓았습니다!

---

이렇게 코드업 2833번 문제를 풀어보았습니다. 앞의 문제와 연계되어 굉장히 쉽게 풀 수 있었던 것 같습니다.