조합 계산하기

문제

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

출력

각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

예제 입력

예제 출력


1
5
67863915

풀이 방향 설정

문제를 이해하고 나면 확률과 통계에서 많이 본 듯한 느낌이 강하게 든다.

이 문제의 예시 케이스 중 하나를 수학문제로 바꿔보면 대충 아래와 같다.

그럼 이 문제를 풀기 위해서는 어떻게 하면 될까?

간단하다. Y에서 X의 원소 개수만큼을 순서를 생각하지 않고 뽑으면 된다. 위 예시에서는 5개 중 3개를 뽑고 나면 자동적으로 크기도 결정된다.

즉 조합* 계산을 사용하면 답을 구할 수 있다. 위 케이스의 답은 5C3 = 10 이겠다.

*조합: 서로 다른 n개에서 순서를 고려하지 않고 서로 다른 r(0≤r≤n)개를 택하는 것을, n개에서 r개를 택하는 조합(Combination)이라 하고, 기호 nCr로 나타낸다.

Sol 1) 조합 공식 & 반복문 사용

이 공식을 활용해서 분모에는 1부터 r까지 곱한 값, 분자에는 n-r+1부터 n까지 곱한 값을 두고 계산하면 nCr을 구할 수 있다. 그리고 분모와 분자 계산은 각각 for문으로 구현할 수 있다.


#include <stdio.h>

long long calc(int n, int m) { //mCn
	long long child = 1;
	long long  parent = 1;
	for (int i = m; i >= m-n+1; i--) { //mPn
		child = child * i;
	}
	for (int i = 1; i <= n; i++) { //n!
		parent = parent * i;
	}

	return child / parent;
}

int main() {
	int size;

	scanf("%d", &size);

	for (int i = 0; i < size; i++) {
		int n, m;
		scanf("%d %d", &n, &m);
		printf("%lld\n",  calc(n, m));
	}
}

그러나 채점 결과 25% 정도에서 실패 케이스가 발생했다.

long long 자료형 범위를 넘어버린 것으로 보인다. ~~자료형 공부 해야겠따~~

큰 범위의 계산인 동시에 나눗셈 연산이 필요한 경우에는 double을 사용하는 것이 좋아보인다.

double: -/+ 0.000,000,000,000,01 to +/- 99,999,999,999,999.9 (at 100% accuracy, with a loss in accuracy starting from 16th digit, as represented in "-1.79769313486232e308 .. 1.79769313486232e308".)

long: -9,223,372,036,854,775,808 to +9,223,372,036,854,775,807

이라고 한다.

double로 변경


#include <stdio.h>

double calc(int n, int m) {
    double child = 1;
    double parent = 1;

    for (int i = m; i >= m - n + 1; i--) {
        child = child * i;
    }

    for (int i = 1; i <= n; i++) {
        parent = parent * i;
    }

    return child / parent;
}

int main() {
    int size;

    scanf("%d", &size);  

    for (int i = 0; i < size; i++) {
        int n, m;
        scanf("%d %d", &n, &m);
        printf("%.lf\n", calc(n, m)); 
    }
}

ㅤ	메모리	코드 길이
맞았습니다!!	1116 KB	460 B

성공!

했지만 더 해보자.

Sol 2) 분자와 분모를 한꺼번에 계산하기


#include<stdio.h>
int main(void)
{
	int size, n, m, result;
	scanf("%d", &size);
	for(int z=0; z<size; z++)
	{
		result=1;
		scanf("%d %d", &n, &m);
		for(int i=0; i<n; i++)
		{
			result*=m-i; 
			result/=1+i;
		}
		printf("%d\n", result);
	}
}

result*=m-i; 는 분자인 (n-r+1)(n-r+2)....(n)

result/=1+i; 는 분모인 r! 을 나타낸 것이다.

ㅤ	메모리	코드 길이
맞았습니다!!	1112 KB	245 B

Sol 3) 조합 공식 & 재귀함수 이용

오른쪽에 추가된 등식을 활용해보자.

우선 재귀함수로 팩토리얼을 계산하는 함수를 만들어주고, 공식대로 계산해주면 된다.



#include <stdio.h>

double factorial(int n) {
	if (n == 0)
		return 1;
	return n * factorial(n - 1);
}

double combination(int n, int m) {
	return factorial(n) / (factorial(n - m) * factorial(m));
}

int main() {
	int size, n, m;

	scanf("%d", &size);
	for (int i = 0; i < size; i++) {
		scanf("%d %d", &n, &m);
		printf("%.lf\n", combination(m, n));
	}
}

ㅤ	메모리	코드 길이
맞았습니다!!	1116 KB	356 B

Sol 4) 조합 성질 이용(파스칼의 삼각형)

조합의 점화식*을 구해보면 다음과 같다.

n-1 C r-1 : 어떤 특정한 원소를 포함해 뽑았을 때

n-1 C r : 어떤 특정한 원소를 포함하지 않고 뽑았을 때

→ 두 가지의 경우를 합하면 n개 중 하나를 뽑는 경우의 수

*점화식 : 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것

이는 파스칼의 삼각형으로도 이해해볼 수 있다.

출처 : https://m.blog.naver.com/saomath/221948595533

이를 코드로 구현하면 아래와 같다.


#include <stdio.h>

double combination(int n, int m) {
	if (n == m)
		return 1;
	if (m == 1)
		return n;
	return combination(n - 1, m - 1) + combination(n - 1, m);
}

int main()
{
	int size, n, m;

	scanf("%d", &size);
	for (int i = 0; i < size; i++) {
		scanf("%d%d", &n, &m);
		printf("%.lf\n", combination(m, n));
	}
}

하지만 시간 초과 난다.

ㅤ	메모리	코드 길이
시간 초과	-	321 B

Sol 5) DP(다이나믹 프로그래밍) 적용

다이나믹 프로그래밍(D.P.)란?

큰 문제를 작은문제로 나누어 푸는 것.

동적 계획법이란 말 때문에 어떤 부분에서 동적으로 프로그래밍이 이루어지는 찾아볼 필요가 없습니다.

작은 부분 문제들이 반복되는 것(답이 바뀌지 않음)을 이용해 풀어나가는 방법이다.

모든 작은 문제들은 한번만 풀어야 하며, 따라서 정답을 구한 작은 문제를 어딘가에 메모해놓는다(메모이제이션). 다시 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과를 재사용한다.

다이나믹 프로그래밍은 다음과 같은 조건하에 사용할 수 있다.

- 작은 문제가 반복됨

- 같은 문제는 구할 때마다 정답이 같음

i개의 서쪽 사이트와 j개의 동쪽 사이트를 잇는 다리를 지을 수 있는 경우의 수를 dp[i][j]로 두고 규칙을 나열해보자.

dp[1][1] = 1	ㅤ	ㅤ	ㅤ
dp[1][2] = 2	dp[2][2] = 1	ㅤ	ㅤ
dp[1][3] = 3	dp[2][3] = 3	dp[3][3] = 1	ㅤ
dp[1][4] = 4	dp[2][4] = 6	dp[3][4] = 4	dp[4][4] = 1
…	ㅤ	ㅤ	ㅤ

1번과 같이 1이 a와 이어진 경우 n-1개의 사이트와 m-1개의 사이트를 잇는 경우의 수를 구하는 것과 같다. → dp[1][3]

2번과 같이 1이 b로 이어진 경우 n개의 사이트와 m-1개의 사이트를 잇는 경우의 수를 구하는 것과 같다. → dp[2][3]

dp[2][4] = dp[1][3] + dp[2][3]

따라서 다음과 같은 식을 만들 수 있다.