[백준/BOJ][C++] 1010번 다리 놓기

<문제 소개>

---

<소스 코드>

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	// 쓰레드 환경이 아닐때 버퍼를 분리하여 처리속도를 빠르게 해줌
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T;
	cin >> T;

	vector<long long> output;

	for (int i = 0; i < T; i++)
	{
		int N, M;
		cin >> N >> M;

		int gap = min(M - N, N);
		
		long long x = 1; // 분자
		long long y = 1; // 분모

		for (int j = 1; j <= gap; j++)
		{
			x *= M - j + 1;
			y *= j;
		}

		output.push_back(x / y);
	}

	for (int i = 0; i < output.size(); i++)
	{
		cout << output[i] << "\n";
	}

	return 0;
}

---

<풀이과정>

1. T를 입력받고, 결과물들을 담을 output을 long long형 벡터로 선언한다.

2. 먼저, 이 문제를 풀 때 중요한 원리는 조합이다.

3. 다리끼리 겹치면 안되기 때문에 왼쪽 사이트는 자신의 밑의 사이트보다 위로 다리가 연결되어야 한다.

4. 즉, 왼쪽은 순서가 정해져 있다는 뜻이다. 그러므로 오른쪽 사이트에서 왼쪽 사이트의 개수만큼 중복되지 않게 고르는 경우의 수를 구하여 왼쪽의 위쪽 사이트부터 순서대로 연결시키면 된다.

5. 따라서 오른쪽 사이트의 갯수 M과 왼쪽 사이트의 갯수 N의 조합을 구하면 된다. (mCn을 구하면 됨)

6. T만큼 반복하며 N과 M을 입력받고, M-N과 N 중 작은 값을 gap으로 저장한다.(작은 값이 계산이 더 쉽기 때문)

7. long long형으로 분자 x, 분모 y를 선언하고 1로 초기화 시킨다.

8. 1부터 gap까지 반복하며 분자 x는 M부터 1씩 빼가면서 곱해주고, 분모 y는 1부터 1씩 더해주며 곱해준다.

9. 이렇게 나온 x와 y를 이용해 output에 x/y를 넣어준다.

10. 모든 반복이 끝난 뒤 output의 원소들을 하나씩 출력해준다.

---

<코멘트>

조합의 성질을 이용해서 어렵지않게 풀었다!

문제의 원리만 이해하면 쉬운듯!

---

<제출결과>