백준 1010번 - 다리 놓기

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

1010번: 다리 놓기

고3때 배운 조합 개념이 나온다.

nCr을 그냥 코드로 잘 구현하면 된다.

처음엔 nCr이 

n! /  ( (n-r)! * r! ) 이니까 이걸 그대로 다 구현해서 하니, 메모리 범위를 너무 넘어섬. unsigned long long으로 해도 마찬가지.

그래서 좀 줄여서 생각해본게 n! / n-r!  * 1/r!인데.. 아래 코드가 저렇지만 

우선 돌려보면 그래도 이 n!하는게 값이 너무 커서 범위 초과로 오류가 나는 것 같다.

#include <iostream>

using namespace std;

long long factorial(int M, int N);
long long factorial(int n);

int main()
{
	int test = 0;
	cin >> test;

	int N, M;
	for (int i = 0; i < test; i++)
	{
		cin >> N >> M;
		if (N == M)
		{
			cout << 1 << endl;
			continue;
		}
		if (M / 2 > N)
		{
			cout << factorial(M, N) / factorial(N) << endl;
			continue;
		}
		else
		{
			cout << factorial(M, M - N) / factorial(M - N) << endl;
			continue;
		}
		return 0;
	}
}

long long factorial(int M, int N)
{
	long long sum = 1;
	int interval = M - N;
	for (int i = M; i > interval; i--)
	{
		sum *= i;
	}
	return sum;
}

long long factorial(int n)
{
    long long sum = 1;
	for (int i = n; i > 0; i--)
	{
		sum *= i;
	}
	return sum;
}

이것인데... VS로 돌리면 결과는 맞게 나오는데, 백준에선 틀린다고 나온다.

그래서 한번 더 생각해보니, 굳이 factorial1 / factorial2 로 하나씩 구해서 나눠야하나 싶었다.

처음부터 식을 구할 때 그냥 곱하고 바로 나누면 범위 초과는 나오지 않으니까.

#include <iostream>

using namespace std;

int main()
{
	int test = 0;
	cin >> test;

	int N, M;
	for (int i = 0; i < test; i++)
	{
		long long result = 1;
		cin >> N >> M;

		for (int j = 0; j < N; j++)
		{
			result *= M - j;
			result /= j + 1;
		}
		cout << result << endl;
	}
	return 0;
}

오늘의 교훈) factorial 하면 자료형 범위 초과할 수 있으니까 잘 생각해보고 안된다 싶으면 바로 곱하고 나누고도 생각해보자.