1010번: 다리 놓기

문제는 다음과 같습니다.

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

1010번: 다리 놓기

 

유의해야할 점은 시간 제한입니다.

0.5초밖에 주어지지 않습니다. 기존 문제들이 2초 가량 준다는 점을 고려하면 굉장히 짧은 시간

입니다.

 

문제를 보시자마자 조합이 떠오르실 겁니다. 그리고 조합의 수식은 다음과 같습니다.

조합을 떠올리는 것 까지는 어렵지 않을 것이라 생각됩니다. 하지만 문제는 팩토리얼 (n!) 구현입니다.

가장 기본적인 방법은 함수를 사용하는 방법이며, 대부분 재귀함수나 for문을 활용한 함수를 떠올릴 것입니다.

int factorial(int n) 
{
	if (n <= 1)
    	return 1;
    else
    	return n*factorial(n-1);
}

int factorial2(int n)
{ 
	int result = 1;
    for (int i = 1; i <= n; i++)
    	result *= i;
    return result;
 }

하지만 수가 30까지 가능하기 때문에 이러한 방법을 사용하게 되면 0.5초 내로 해결할 수 없습니다.

for문을 최대한 적게 사용하면서 구현하는 방법은 다음과 같습니다.

#include <iostream>
using namespace std;

int main() {
	int num;
	cin>>num;
	for(int i{0};i<num;i++)
	{
		int n,r;
		cin>>n>>r;
		long long result =1;
		for(int j{0};j<n;j++)
		{
			result*=r-j;
			result/=j+1;
		}
		cout<<result<<endl;
	}
	
	return 0;
}

곱하는 과정과 나누는 과정을 동시에 처리하면서 한 번으로 값을 구현할 수 있습니다.

이 과정을 찾는 것이 중요한 문제라고 생각합니다.