[백준] 1010 다리놓기 (조합의 수) n개에서 m개 뽑기

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

1010번: 다리 놓기

 

 

초반 생각한 방식은 m개중 n 개를 뽑으면 자동으로 된다고 생각했다. 그래서 익숙한 dfs로 길이가 n인 조합을 구했는데 

시간초과가 떳다...ㅎ 

경우의 수만 구하면 되는 거니까 수학공식을 사용해서 하면 될것이라고 생각해서 했지만 

결과값이 int 가 담을 수 없는 숫자라서 실패

그래서 타입을 long long 에서 unsigned long long 으로 변경한 후 해봤지만 시간초과... and 50% 에서 실패

 

(n개 중에서 m개를 뽑는 조합의 가짓수​)=(n개 중에서 m개를 뽑는 순열의 가짓수)÷m!

=

=​

 

 

질문검색을 해본 결과

n에서 m 개를 뽑는 경우의 수는 n에서 (n-m) 개를 뽑는 경우의 수와 동일하다

에서 힌트를 얻고 if (m/2 < n) n = m-n 를 추가했다

 

그 결과 성공

#include <iostream>
#include <vector>
using namespace std;
int n, m;
int t;

// m 개중에서 n을 뽑기
unsigned long long choice(int n, int m) {
	unsigned long long a = 1;
	unsigned long long b = 1;

	for(int i=m; i>=(m-n+1); i--)
		a = a * i;

	for(int i=n; i>=1; i--)
		b = b*i;

	return a / b;
}

int main() {

	scanf("%d", &t);

	while(t--) {

		scanf("%d %d", &n, &m);

		if(m/2 < n) n = m-n;
		unsigned long long answer = choice(n, m);

		printf("%llu\n", answer);

	}

}