[백준] 1010. 다리 놓기

: solved.ac (자율) - silver 5

 

https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

 

예제 입력

3
2 2
1 5
13 29

 

예제 출력

1
5
67863915

 

정답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int t, d, n, m;
	long long int v;

	scanf("%d", &t);


	for (int i = 0; i < t; i++) {
		scanf("%d %d", &n, &m);

		if (n > m / 2) n = m - n;
        
		v = 1;
		for (int j = m; j > m - n; j--) {
			v *= j;
		}

		d = 1;
		for (int j = m; j > m - n; j--) {
			v /= d;
			d++;
		}
        
		printf("%lld\n", v);
	}

	return 0;
}

---

해설

 

: 조합(Combination)을 이용한다.

 

확률과 통계 등에서 배워 본 적이 있을 것이다. m개의 대상 중 n개를 (순서를 따지지 않고) 고를 수 있는 경우의 수를 조합이라고 하고, Combination의 C를 따서 mCn이라고 표기한다. 계산 방법은 다음과 같다.

위의 수식을 그대로 코드로 옮기면 된다. 서쪽의 사이트 갯수가 언제나 동쪽의 사이트 갯수보다 적다는 조건이 있기 때문에 다리를 놓는 것은 '동쪽 사이트 중에서 서쪽 사이트와 연결할 사이트 n개를 고르는' 문제가 될 것이며,

다리가 서로 겹치지 않도록 해야 한다는 조건이 있으므로 연결될 순서는 언제나 정해져 있는 것과 마찬가지일 것이다.

위의 이유로 이 문제는 조합 문제의 성질을 띤다.

 

구현 시 신경써주어야 할 사항은 다음과 같다.

 

1. 오버플로우: 29! 까지도 계산해야 하는 경우가 생기기 때문에, long long int형의 변수가 필요하다.

 

2. 시간 초과: 29C24처럼 골라야 할 수가 크다면 팩토리얼 계산이 길어져 시간 초과가 생길 수 있다.

그러므로 여기서는 조합의 성질(29C24와 29C5는 서로 값이 같다)을 이용하여

n이 m의 절반보다 클 경우 m-n을 n 변수에 대신 넣어주어야 한다.

 

3. 테스트케이스의 갯수: 테스트케이스의 갯수 t는 문제에서 따로 범위를 지정해주지 않았다.

때문에 배열 등의 자료형으로 일일이 저장하는 것은 공간의 크기를 가늠할 수 없어 불가능하므로

t만큼의 for문을 돌려 그때그때 입력받고 계산하여 출력해야 한다.

 

 

 

 

 

 

코드의 각 부분은 다음과 같은 기능을 갖는다. 필요한 각종 변수들을 선언하고, t를 입력받는다.

위에서 설명했던 대로 for문을 돌려 서쪽 사이트 갯수인 n과 동쪽 사이트 갯수인 m을 입력받은 후,

시간초과 방지를 위해 n값을 조정해 준다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int t, d, n, m;
	long long int v;

	scanf("%d", &t);

	for (int i = 0; i < t; i++) {
		scanf("%d %d", &n, &m);

		//시간초과 방지 - n이 m의 절반보다 클 경우
		//n을 m-n 값으로 바꾸기
		if (n > m / 2) n = m - n;

 

다리갯수를 계산할 변수 v를 초기화해준 뒤 조합 식의 분자 부분을 계산한다.

재귀를 통해 계산할 수도 있으나 for문을 통해 계산하는 편이 더 간결하다고 생각해 해당 방식을 채택했다.

차례로 수를 곱해준 뒤 분모 팩토리얼을 계산한다.

따로 분모 변수를 만들어줄 필요 없이 나눠주는 수를 1씩 증가시키며 for문을 통해 나눠주기만 하면 된다.

		v = 1;

		//분자 팩토리얼(일부) 계산
		for (int j = m; j > m - n; j--) {
			v *= j;
		}

		d = 1;
		//분모 팩토리얼 계산
		for (int j = m; j > m - n; j--) {
			v /= d;
			d++;
		}
		printf("%lld\n", v);
	}

	return 0;
}