백준 BOJ 1010 - 다리 놓기

오늘 수학학원에서 배운 내용이 사실상 그대로 나왔다.

그냥 M개중에 N개 뽑아서

순서대로 할당해주면

겹치지 않게 다리를 놓을 수 있다

그렇게 보면 이 문제는 단순히 mCn을 구하는 문제로 변한다.

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

1010번: 다리 놓기

#include <stdio.h>
typedef long long int ll;

ll nCr(ll n, ll r){
	ll sum = 1;
	for(int i=0; i<r;  i++){
		sum*=(n-i);
		sum/=(i+1);
	}
	return sum;
}

int main(){
	int n,m,t;
	scanf("%d", &t);
	while(t--){
		scanf("%d %d", &n, &m);
		printf("%lld\n", nCr(m,n));
	}
	return 0;
}

오버플로우가 날 수 있으므로 매번 나눠주어야 한다

간단히 AC.