다리 놓기 풀이

문제 링크: https://www.acmicpc.net/problem/1010

백준 정수론 및 조합론 9단계 - 1010번 다리 놓기를 풀어보았다.

 

풀이: dp로 풀어볼까 했지만, 그냥 계산하는 게 나은 거 같았다.

 

C++

#include <iostream>

using namespace std;

int main()
{
	int t;
	cin>>t;
	for(int i=0;i<t;i++)
	{
		int n,m;
		cin>>n>>m;
		int nn;
		if(n>=m-n) nn=n;
		else nn=m-n;
		long long res=1;
		for(int j=1;j<=m-nn;j++)
		{
			res=int(res*(m+1-j)/j);
		}
		cout<<res<<'\n';
	}
}

Python

t=int(input())
for i in range(t):
	n,m=map(int,input().split())
	if n>=m-n: nn=n
	else: nn=m-n
	res=1
	for j in range(1,m-nn+1):
		res=int(res*(m+1-j)/j)
	print(res)

Java