[백준][C++] 1010: 다리 놓기

문제 링크: https://www.acmicpc.net/problem/1010

 

다리를 놓아야 하는데 겹칠 수 없게 놓아야 한다고 합니다.

문제를 약간 다르게 생각해보면, 동쪽 도시중에 다리를 놓지 않을 M-N개 도시를 구하면 됩니다. 그러면 아래와 같이 식을 세울 수 있습니다.

\[_M \mathrm{C} _{M-N} = \binom{M}{M-N} \]

이항계수 문제로 바꿀 수 있는데 이항계수를 DP로 구현하면 끝입니다.

그런데 이 문제는 N, M의 최대값이 30으로 적기 때문에 dp를 안쓰고 백트래킹으로 풀어도 통과는 될 듯 합니다 (아마도)

#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;


const int INF = 987654321;
typedef long long ll;


int dp[31][31];

int bino(int n, int r) {
	if (r == 0 || n == r) return 1;

	int &ret = dp[n][r];
	if (ret != -1) return ret;

	ret = bino(n - 1, r - 1) + bino(n - 1, r);

	return ret;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	memset(dp, -1, sizeof(dp));

	int t;
	cin >> t;
	while (t--) {
		int n, m;
		cin >> n >> m;
		cout << bino(m, m - n) << '\n';
	}
	
	return 0;
}

top-down 방식으로 풀어봤습니다