코드업 2833 : [상태 정의를 통한 탐색] 계단 오르기 2-1

https://halfand.tistory.com/13

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

 

코드업 시리즈 2번째

 

지금 시작합니다

 

 

당신은 굿이에요                     당신은 그뤠잇해요

 

 

---

 

문제

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

철수가 계단을 올라가려고 한다.

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

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

철수가 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]

 

출력

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

 

입력 예시

3 3

 

출력 예시

3

 

---

MY CODE

#include <stdio.h>
int n, k;
int count(int nn, int kk){
    if(nn==0) return 1;
    else if(kk==0) return 0;
    return count(nn-1, kk-1) + count(nn-2, kk-1) + count(nn-3, kk-1);
}

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

 

코드설명

int count(int nn, int kk){
    if(nn==0) return 1;
    else if(kk==0) return 0;
    return count(nn-1, kk-1) + count(nn-2, kk-1) + count(nn-3, kk-1);
}

//nn이 0일 때, 즉 더 이상 올라갈 계단이 없을 때 1을 반환한다.

//kk가 0일때, 즉 더 이상 밟을 수 있는 계단의 수가 없을 때 0을 반환한다. 

//각각 1칸의 계단을 오르는 경우, 2칸의 계단을 오르는 경우, 3칸의 계단을 오르는 경우이다. 

 

이런 느낌으로 재귀함수가 돌아가는 거라고 보시면 됩니다.

 

 

---

 

생겼던 문제점

사실 처음에는 제가 2832번에 썼던 nCr 방식을 여기서도 적용해 보려고 했었습니다.

근데 그렇게 되면 확실한 지는 모르겠지만 nCr * nCr......? 혹은 nCr * n * 1/2 정도의 답없는 값이 나와야 하더라고요.

 

 

아이디어 적은 노트

 

이건 아니다 싶어 급히 경로를 틀었습니다. 제 방식의 한계는 2832번이었습니다....

물론 이번에도 불가능한 것은 아니겠으나 너무너무너무 코드가 더러워져서 다른 방식을 찾는 쪽으로 바꿨습니다.

 

만들다 만 코드. 저 for문 안에서 각각 nCr을 돌리고 그만큼 또 돌려야 한다...

 

---

순서도

 

 

---

 

깔끔하게 정리되어 쌓여가는 글들을 보니 꽤나 마음이 뿌듯해지는 것 같습니다. 정말 열심히 적었기도 했고요.

정말 아무것도 모르는 생 초짜가 내 글을 보고 이해할 수 있으면 좋겠다! 라는 마음으로 친절하게 적으려고 노력했습니다.  

 

여튼 제 긴 글들을 읽어주셔서

 

 

다들 파이팅