문제는 진작 풀었으나 이제야 올리는 코드업 2832번 티스토리
지금 시작합니다
1시간 30분동안 열심히 적은 글이 날아갔습니다.
다시 시작합니다.
문제
코드업 2832번: [상태 정의를 통한 탐색] 계단 오르기 1-1
철수가 계단을 올라가려고 한다.
계단은 모두 n칸으로 구성되어 있다.
철수는 한 번에 1칸, 2칸을 오를 수 있다.
철수가 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]
출력
계단을 올라가는 서로 다른 경로의 수를 출력한다.
입력 예시
3 3
출력 예시
2
처음 문제를 읽고 나서 든 생각은
(뭔가 나만의 새로운, new, 新, Nouveau, Новый, नया, baru, 암튼 그러한 풀이를 찾고 싶다.)
O
. o
였습니다.
그러다 처음 생각해 냈던 것은 이진법을 이용한 계산이었는데요.
** 이진법이란? **
이진법(二進法, binary)은 두 개의 숫자(1과 0)만을 이용하는 수 체계이다. 관습적으로 0과 1의 기호를 쓰며 이들로 이루어진 수를 이진수라고 한다. -위키백과-
철수가 올라갈 수 있는 계단의 수는 2칸 또는 1칸이므로, 올라가는 계단의 수를 나열하면 212221211... 처럼 2와 1의 배열이 됩니다. 이때 각 자리에서 -1을 해 주면 101110100...이 되므로 이진법을 사용해서 계산을 해도 좋을 것이란 생각이 든 거죠.
그러나 조금 코드를 생각해 보면 c언어에서 이진법으로 수를 바꾼 후에 이진법으로 연산을 하는 것이 번거롭다는 것을 알 수 있습니다. 구현이 불가능 한 것은 아닐 것 같으나 코드가 길어질 것 같아, 안타깝지만 이 아이디어는 일단 접어두게 되었습니다.
언젠가 시간이 나면 이 방법으로도 한 번 도전해 보려 합니다! (믿는다 나자신...)
그렇다면 저는 어떤 아이디어를 가지고 문제를 풀었을까요?
또 고민을 하다가, 그날 점심을 먹는 도중 아이디어가 생각났습니다.
신나서 먹던 점심을 뒤로 하고 혹시나 잊어버릴까봐 후다닥 제 패드에다가 메모했습니다.
(밥먹다 갑자기 뛰쳐나가서 앞에 있던 애들이 뭐야 저거 하는 표정을 짓더라고요ㅋㅋㅋㅋㅋㅋㅋ)
그렇게 제가 떠올려낸 또 다른 아이디어는 nCr, 즉 조합을 이용한 풀이였습니다.
** 조합이란? **
수학에서 조합(組合, 문화어: 무이, 영어: combination)은 유한 개의 원소에서 주어진 수만큼의 원소들을 고르는 방법이다. 조합의 수는 이항 계수로 주어진다. -위키백과-
설명이 조금 딱딱하죠? 쉽게 말하자면 조합이란, n개의 원소에서 r개만큼의 원소를 고르는 방법을 말합니다.
그럼 앞에서 말했던 nCr이란 무엇일까요? 그건 조합의 수를 구하는 공식을 보면 알 수 있습니다.
여기서 nCr은 n개의 원소중에서 r개만큼의 원소를 고르는 조합의 개수를 말합니다.
따라서 조합의 수를 구한다 == nCr을 구한다 라고 말 할 수 있는 거죠.
핵심 idea
n이 짝수일 때 (2칸 올라가는 것을 2, 1칸 올라가는 것을 1이라고 두었습니다.)
1. 가장 적은 계단을 밟고 올라가는 방법 : 22222....22
2. 그 다음으로 적은 계단을 밟고 올라가는 방법: 위의 숫자들에서 2를 하나 빼고 1을 2개 넣었을 때 nCr 값 (n은 1에서 2의 개수, r은 1의 개수)
- 왜 nCr인가?
1이 1개일 때의 계단을 오르는 방법의 수는
22222...21, 22222...12, ....... , 21222...22, 12222...22로 총 2의 개수만큼일 것이기 때문.
홀수일 때는 마지막 2를 1로 바꾼 후에 똑같이 세면 됩니다.
이제 본격적으로 제가 짠 코드를 설명하겠습니다.
MY CODE
#include <stdio.h>
int n, k;
int noc;
long long int fac(int a){
if(a==1||a==0) return 1;
return a*fac(a-1);
}
int ncr(){
int i=0, n2=n/2;
if (n%2){
i++; n2++;
}
for(; n2<k&&n2>i; n2++, i+=2){
noc+=fac(n2)/(fac(n2-i)*fac(i));
}
return noc;
}
int main(){
scanf("%d%d", &n, &k);
printf("%d", ncr());
return 0;
}
원래는 코드에 주석을 달려고 했는데 너무 길어지다 보니 글을 발행했을 때는 코드가 이상해 지더라고요.
하지만 그냥 넘어갈 수는 없죠. 아래에서 차근차근 설명해 드리겠습니다.
(생략)
int noc;
//noc: number of cases, 계단을 오르는 경우의 수
long long int fac(int a){
if(a==1||a==0) return 1;
return a*fac(a-1);
}
//factorial 계산 함수
//a가 1이 되면 더 재귀를 돌리지 않아도 되므로 지금까지 곱한 값을 반환하며 함수를 종료합니다.
//팩토리얼의 정의에 따르면 0!=1이라고 합니다.
int ncr(){
int i=0, n2=n/2;
if (n%2){
i++; n2++;
}
//i는 1칸 올라가는 횟수, n2는 (최소한의 계단만 밟고 n번째 계단까지 올라갈 때 밟는 계단의 수 - 1)입니다.
(왜 -1을 할까요? 한 번 생각해 보세요!)
//n이 짝수이면 (예를 들어 n==6) 2칸+2칸+2칸 올라가서 총 n/2인 3칸만 밟으면 되지만 n이 홀수일 시에는 (예를 들어 n==5) 2칸+2칸+1칸 올라가야 하기 때문에 밟는 계단의 수가 (n/2)+1=3개입니다.
for(; n2<k&&n2>=i; n2++, i+=2){
noc+=fac(n2)/(fac(n2-i)*fac(i));
}
return noc;
//i+=2인 이유: 한번에 2칸 올라가던 것을 한 칸씩 올라가려면 밟는 계단의 수가 *2가 되기 때문입니다.
//위에서 봤던 nCr공식을 factorial 함수를 이용해 구현한 것입니다.
과정 설명 순서도
생겼던 문제점
제가 한번에 뿅 코드를 짜 내지는 않았겠죠? 많은 시행착오를 겪으며 만들어진 코드입니다...
for(; n2<=k&&n2>i; n2++, i+=2)이것은 문제가 있던 코드의 일부분인데요. 정확한 풀이가 나오는 코드와 어느 부분이 다른지 눈치 채셨나요?
정답은 n2 <= k 부분입니다. 정확한 풀이가 나오는 코드에는 등호가 들어가 있지 않습니다.
그렇다면 왜, n2 <= k 라는 조건에서는 오답이 나오는 걸까요?
이건 제가 코드를 짤 때 메모한 것인데요.
위 사진을 보시면
라고 적어놓은 부분이 있습니다.
이것은 n=6, k=5일때의 조합이 가능한 경우를 직접 나열해 본 것입니다.
보시면 2가 3개인 경우 1개, 2가 2개고 1이 2개인 경우 6개, 2가 1개고 1이 4개인 경우(5개일 것이므로 생략했음)를 적어놓았는데요. 위에 적어놓은 바에 따르면 n=6일때, k=5일때의 답은 1+6+5로 12개가 나와야 합니다.
그러나 정확한 코드에 n=6과 k=5를 넣어 보면
답이 12가 아니라 7이 나오는 것을 볼 수 있습니다.
제가 여기서 저지른 실수는, 바로 0번째 계단을 생각하지 않고 코드를 짰던 것인데요.
222와 2211, 21111 모두 각 자리의 합이 6, 즉 n이 되기 때문에 21111의 경우도 가능하다고 생각했던 것이 문제였습니다.
그러나 각 자리의 2와 1의 합이 n이 된다는 것은 k개 이하의 계단을 밟는 것이 아닌, n개의 계단을 오르기 위한 조건이었습니다.
위 그림과 같이 21111은 0번째 계단(바닥)까지 포함하여 총 6계단을 밟고 올라가는 것이 되기 때문에, 5인 k의 값보다 더 커지게 되어 문제가 생기게 되었던 것입니다.
결국 제가 처음에 잘못 생각했던 n2는 0번째 계단을 빼고 밟고 올라간 계단의 개수였습니다.
즉, n2의 진짜 의미란 ( 계단을 최대한 적게 밟고 올라가는 수 - 1 )이 되는 것이죠.
이제 왜 제가 위 주석에서 -1을 했는지 이해하실 수 있을 거에요!
여담
Q. 왜 fac 함수에서는 int가 아니라 long long int를 사용했는가?
- A. 그냥 int 썼다가 오버플로우 당함...
마무리하며...
긴 글 읽어주셔서 감사합니다.
아래는 코드업 2832번의 링크입니다. 저의 코드만이 이 문제를 해결하는 유일한 정답은 아니기 때문에, 제 글을 보신 분들도 한 번 본인만의 코드를 짜서 문제를 해결해 보시기를 바랍니다. 파이팅!!
https://codeup.kr/problem.php?id=2832&rid=23179
[상태 정의를 통한 탐색] 계단 오르기 1-1
OO이가 계단을 올라가려고 한다. 계단은 모두 n칸으로 구성되어 있다. OO이는 한 번에 1칸, 2칸을 오를 수 있다. OO이가 k개 이하의 칸을 사용하여 0번째 칸에서 출발하여 n번째 칸으로 올라가는 서
codeup.kr
저는 그럼 이만 다음 과제를 하러 가보겠습니다. (살려주세요)
'정보 AP' 카테고리의 다른 글
| 2651 : 극장 좌석 배치 1 (0) | 2023.06.01 |
|---|---|
| 2653 : 규칙에 맞는 이진수 만들기 (Small) (0) | 2023.05.31 |
| 코드업 2610 : 그림판 채우기 (0) | 2023.05.12 |
| 코드업 2636 : 먹느냐 먹히느냐 (0) | 2023.05.11 |
| 코드업 2833 : [상태 정의를 통한 탐색] 계단 오르기 2-1 (0) | 2023.03.31 |