백준 1010

www.acmicpc.net/problem/1010

1010번: 다리 놓기

#include <iostream>
#include <vector>
#include <algorithm>//max min을 위함
using namespace std;
long long npr = 1;


int main()
{
	int N, M;
	int T;//테스트케이스 개수
	int top, bottom;//nPr n=top,r=bottom
	cin >> T;
	for (int i = 0; i < T; i++)
	{
		cin >> N >> M;
		top = max(N, M);
		bottom = min(N, M);
		
		if ((top - bottom) >= bottom)
		{
			int temp = top;
			while (top > (temp - bottom))
			{		npr *= top;
					top--;
			}
			for (int i = 1; i <= bottom; i++)
			{
				npr /= i;
			}
		}
		else
		{
			int temp = top - bottom;
			while (top > bottom)
			{
				npr *= top;
				top--;
			}
			for (int i = 1; i <= temp; i++)
				npr /= i;
		}
		cout << npr<<endl;
		npr = 1;
	}


}

간단한 조합문제다 중학교 수학시간 조합 공식만 잊지 않았다면 쉽게 풀 수 있다.

(나도 사실 까먹었나보다 nPr로 적은거보니 ㅎㅎ;)

for문으로 n!하고 r!나누고, (n-r)!나눠주면 되겠지! 하고 돌려보니 값이 longlong으로 커버가 안된다.

따라서 두가지 경우의 수로 나누어야한다

(n-r)>r 일때 or r>(n-r)일때 로 구분하여 n!을 계산 할 때 최소한의 값만 곱하여 자료형의 초기화를 미연에 방지하였다.

이후 나머지 펙토리얼을 나눠주며 출력하면 끝