2651 : 극장 좌석 배치 1

안녕하세요. 소 약간 잃은 뇌입니다.

오늘 제가 가져온 문제는 코드업 2651 : 극장 좌석 배치 1 입니다.


문제

극장에 n개의 빈 좌석이 있다.

k명의 관객들이 영화를 보기 위해서 왔다.

이 관객들이 n개의 좌석에 앉을 수 있는 서로 다른 방법의 수를 구하는 프로그램을 작성하시오.

(단, k명의 사람을 서로 구분하지 않는다.)

 
입력

첫 번째 줄에 n 과 k 가 공백으로 구분되어 입력된다.
 
[입력값의 정의역]
1 ≤ k ≤ n ≤ 20

 
출력

구한 답을 첫 번째 줄에 출력한다.

 
입력 예시

4 2

 
출력 예시

6

 
도움말

- 예제에 대한 설명 

좌석 4개중 2개를 고른 방법(검은색은 사람이 앉은 자리를 의미함)은 다음과 같이 6가지가 존재한다.

◯◯●●, ◯●◯●, ●◯◯●, ◯●●◯, ●◯●◯, ●●◯◯ 

 
 

---

 
문제 설명
 
k명의 사람이 n개의 빈 좌석에 앉아야 합니다. 어디서 많이 본 상황 같지 않나요?
 
바로 중학교때 배웠던 순열과 조합입니다.
 
 
순열은 nPr, 수열은 nCr로 나타내는데요. 
 
순열과 수열의 차이는 무엇일까요?
 
순열은 선택되는 요소의 순서를 서로 구분하지 않고, 조합은 순서를 서로 구별하는 가짓수입니다.
 
 
순열의 식은 n!/k!입니다.
 
이 문제는 k명의 사람을 서로 구분하지 않으므로 사람이 구별되는 가짓수 (n-k)!로 나누어 줘야 합니다.
 
 
따라서 우리는 n! / (n-k)! k!이라는 점화식을 구할 수 있습니다. 
 
 
 
코드

#include <stdio.h>
long long int s;
long long int ff(int a){
    s=1;
    for(int i=1; i<=a; i++){
        s*=i;
    }
    //printf("s: %lld\n", s);
    return s;
}
int f(int n, int k){
    return ff(n)/(ff(n-k)*ff(k));
}
int main(){
    int n, k;
    scanf("%d%d", &n, &k);
    printf("%d", f(n, k));
}

long long int s;

long long int로 하지 않으면 테스트케이스에서 걸립니다... 아무래도 팩토리얼 구현 함수다 보니 수가 엄청 커져서 그런 것 같아요. 꼭 주의하시길 
 

long long int ff(int a){
    s=1;     
    for(int i=1; i<=a; i++){
        s*=i;     
    }     
    //printf("s: %lld\n", s);    
    return s; }

팩토리얼 구현 함수입니다. i가 1에서 n이 될 때까지 for문으로 *= 돌리면 됩니다.
 

return ff(n)/(ff(n-k)*ff(k));

위에서 설명했던 점화식입니다. 
 
 
중간에 들어가 있는 printf함수는... 제가 코드가 이상하다 싶으면 중간중간에 printf를 넣어서 일일이 확인해 보고는 하는데요. 진짜하짓마ㅔㅅ요노가다죽을거같음 이렇게 하면 코드가 어떻게 굴러가고 있는지 확인할 수 있습니다. 좋은방법이에요 다들 꼭 해보시길 바랍니다.
 
(근데 진짜 위에꺼 농담 아니고 곳곳에 printf 넣어두면 dfs 흐름 보는 것이 가능합니다. 꽤나 재밌)
 
 

순서도
 
 

 

 

문제점

 

저는 함수로 기능들을 빼는 것을 좋아해서 간단한 것도 웬만하면 다 함수로 빼 버리는데요. 특히 팩토리얼은 왜인지는 모르겠는데 for보다 걍 재귀로 구현하는 것이 더 먼저 나옵니다. 그래서 이번에도 처음에는 재귀로 팩토리얼 함수를 구현했는데요.

 

뭔가 이상했습니다.

맨 처음 return 안 넣어서 값 안 나온 것을 차치하더라도  ???: 이거 왜 출력이 안 돼?

 

냅다... 시간초과가 떠 버리는 것이었죠.

 

생각해보면 for보다 재귀로 돌리는 것은 매우 비효율적입니다. 구현되는 방법만 조금 생각해도 알 수 있지요. 

 

그런데 이걸 못 생각해내고 뭐가 문제인데 왜 나 꽈찌쭈는 햄보칼수업서 이러면서 코드랑 씨름했다는... 아무튼 그랬습니다. 

 

for로 바꾸니까 바로 잘 돌아가더라고요. 

 

 

느낀점

 

2개의 컴퓨터 언어를 배운다고 둘 다 잘 하는게 아니라.. 하나를 하면 하나가 퇴화되는 느낌입니다. 스탯이 한정되어 있고 얘를 분배하는 느낌이랄까. 재귀로 팩토리얼 구현하는게 바로 안 되는걸 보고(그래봤자 return 안 쓴것 읍읍) 꽤나 충격먹었습니다. 역시 영어든 c언어든 제2외국어는 꾸준히 하는 것이 중요한 것 같습니다.

 

 

아래는 여느때와 다름없이 링크입니다.

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

극장 좌석 배치 1