[Algorithm] BOJ 다리놓기 - 1010번

 

 

 

 

 

 

1. 문제 풀이

다리 놓기는 일직선 모양의 강의 동쪽과 서쪽에 다리를 겹치지 않게 놓을 수 있는 경우의 수를 구하는 문제이다.

서쪽과 동쪽에는 각 N개와 M개의 다리를 둘 수 있는 곳이 있고 0 < N ≤ M < 30 으로 주어진다.

 

 

해당 문제는 위의 경우의 수를 구하는 공식을 통해 풀이했다.

위의 공식을 코드로 옮겼을 시에는 long long 오버플로우로 중복되어 곱해지는 부분을 제외해 주었고

 

제외 할 수는 m - n or n 중 큰수로 m! 계산에서 제거하였다.

 

2 . 코드

 

#include <iostream>

using namespace std;

int main() {

	int m;
	int n;
	int ca;
	//테스트케이스 개수
	cin >> ca;
	//경우의 수
	long long count = 1;

	for (int i = 0; i < ca; i++)
	{
		cin >> n;
		cin >> m;
		int j = 0;
		count = 1;
		// 중복연산 제외할 n 설정
		if (n > m - n)
			n = m - n;
		//m! 연산, n보다 큰 수까지만 곱한다
		while (j < n)
		{
			count *= m - j;
			j++;
		}
		j = 0;
		//count를 n보다 작은 수까지 나눈다.
		while (j < n)
		{
			count /= j + 1;
			j++;
		}
		cout << count << endl;
	}
  	return 0;
}

3. 채점 기록

메모리 : 2016KB / 시간 : 16ms