문제
n명의 사람중 m명을 순서에 상관없이 뽑는 경우의 수를 조합이라고 하며 nCm으로 나타낸다.
이 조합은 파스칼의 삼각형과 아주 밀접한 관련이 있다고 한다.
n과 m이 주어졌을때 nCm의 값을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 n, m(0≤m≤n≤30)이 들어온다.
출력
첫째 줄에 nCm의 값을 출력한다.
예제 입력
5 2
예제 출력
10
이 문제를
#include <stdio.h>
int n,m;
int multiply = 1;
int multiply2 = 1;
int multiply3 = 1;
int main() {
//Please Enter Your Code Here
scanf("%d %d",&n,&m);
for(int i=n; i>0; i--){
multiply = multiply * i;
}
for(int i=m; i>0; i--){
multiply2 = multiply2 * i;
}
for(int i=(n-m); i>0; i--){
multiply3 = multiply3 * i;
}
printf("%d",multiply/(multiply2*multiply3));
return 0;
}
다음과 같이 구현했으나, 시간 초과가 떴다.
그러므로 파스칼 삼각형을 공부해보자.
이항계수의 성질을 알아야만 해결할 수 있어서 파스칼 삼각형의 원리를 공부하였다.
<원리>
nCr + nCr+1 = n+1Cr+1 이다.
예를 들어, 10개 중 2개를 고르는 경우의 수는 45개이다. -> 10 x 9 / 2 x 1;
9C1 + 9C2 = 45이다.
다른 예를 보면, 9개 중 3개를 고르는 경우의 수는 9C3 인데,
8C2 + 8C3 으로 표현된다.
<코드>
#include<stdio.h>
int n,m;
int combi[32][32];
int getCombi(int arr[][32], int l, int k)
{
if(k==1){
// nC1은 항상 n
arr[l][k] = l;
return l;
}
if(k==0){
// nC0 은 항상 1
arr[l][k] = 1;
return 1;
}
if(l==k){
// nCn 은 항상 1
arr[l][k] = 1;
return 1;
}
if(arr[l][k]!=0){
return arr[l][k];
}
arr[l][k] = getCombi(arr,l-1,k)+getCombi(arr,l-1,k-1);
return arr[l][k];
}
int main(){
scanf("%d %d",&n,&m);
printf("%d",getCombi(combi,n,m));
return 0;
}
조합의 문제에서 팩토리얼을 사용하여 재귀 호출로 문제를 풀 경우에는 계산량이 많아져 시간 초과가 발생하는 것을 알 수 있었다.
그러므로 파스칼의 원리와 조합 + (재귀의 흐름) 을 이해하면 조합 문제의 경우 더욱 효율적인 코딩이 가능하다.
'알고리즘' 카테고리의 다른 글
[Algorithm] streetree (0) | 2019.02.02 |
---|---|
[Algorithm] BasicGCD (0) | 2019.02.02 |
[Algorithm] 순열과 조합 (0) | 2019.01.29 |
[Algorithm] sequencenum (0) | 2019.01.29 |
[Algorithm] 런타임 에러가 발생하는 이유 (0) | 2019.01.28 |