코드업 2832번

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

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

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

---

문제 설명

 

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

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

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

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

만약 n = 3, k = 3 이면

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

로 모두 2가지 경우가 있다. 

---

입력

 

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

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

---

출력

 

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

 

문제를 보니, 우리가 많이 본 계단 오르기 문제에 k개 이하의 칸을 이용한다는 조건이 붙었네요.

 

흔히 보는 계단 오르기 문제는 보통 아래와 같은 순서도로 풀이됩니다.

계단을 한 번에 1칸 또는 2칸을 오를 수 있으니, n개의 계단을 오르는 방법의 수는 n-1개의 계단을 오르는 방법의 수 + n-2개의 계단을 오르는 방법의 수 라는 아이디어를 이용한 것이죠.

 

원래의 함수는 몇 칸이 남았는지 알려주는 변수 m만 있었지만, 저는 여기서 k개 이하의 칸을 이용하라는 조건을 맞추기 위해, 함수의 입력값에 이용할 수 있는 칸 수 제한이 얼마나 남았는지를 알려주는 변수 cnt를 추가하였습니다.

cnt가 0이면 더 이상 올라갈 수 없으므로 방법의 수가 0이 되고, 1칸 남았을 때는 방법의 수가 1가지, 2칸 남았을 때는 cnt가 1인 경우는 방법의 수가 1가지 (한 번에 2칸), cnt가 2인 경우는 방법의 수가 2가지 (한 번에 2칸, 1칸 씩 2번)이 됩니다.

 

따라서 이러한 알고리즘의 순서도를 작성해보면 아래와 같습니다.

이러한 알고리즘을 바탕으로, C를 이용하여 코드를 짜보았습니다.

제가 가장 처음에 짠 코드는 아래와 같습니다.

#include <stdio.h>

int k, n;

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

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

이 코드는 처음에 제대로 작동하지 않았습니다. 원인이 무엇인지 살펴보았는데, 0번째 칸, 즉 처음 위치도 k개 이하의 칸을 이용한다는 제약에 포함된다는 사실을 파악하지 못하였고, 2칸이 남고 1개의 칸만 더 이용할 수 있을 때 방법의 수가 1인 것을 간과하여 잘못된 코드를 작성한 것이었습니다. 

 

따라서 아래와 같이 코드를 수정하였습니다.

#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
    {
        return f(m-1, cnt-1) + f(m-2, cnt-1);
    }
  }
}

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

코드를 위와 같이 수정하니, 이제야 제대로 작동하였습니다.

---

이렇게 코드업 2832번 문제를 풀이해보았습니다. 평소 흔히 보던 계단 오르기 문제에 칸 수 제한을 추가한 것이 새로웠던 문제였던 것 같습니다.