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

백준 온라인 저지(BOJ) 1010번 다리 놓기

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

1010번: 다리 놓기

* 사용언어 : C언어, C++

 

1. 문제

N개의 강 서쪽 사이트에서 M개의 강 동쪽 사이트로 N개의 다리를 연결하려 함

다리끼리 겹치지 않도록 다리를 짓는 경우의 수를 출력

 

2. 풀이

결론부터 말하면

M개의 사이트에서 N개를 뽑는 경우의 수, 즉 mCn을 출력하면 됩니다.

 

M개의 사이트에서 N개를 선택한 후 각각의 케이스 별로 가능한 경우의 수는 1입니다.

왜냐하면 다리가 겹쳐질 수 없다는 조건이 있으므로 순차적으로 할당하는 1가지 방법만 있기 때문입니다.

 

따라서 그냥 mCn을 구해서 출력하면 됩니다.

 

 

문제에서 T가 몇인지 주어지지는 않았지만

어쨌든 mCn을 여러 번 구해야 하므로 Dynamic Programming을 이용하여 풀었습니다.

 

파스칼의 삼각형 공식(nCr = n-1Cr-1 + n-1Cr)을 활용하면 되고

불필요한 재귀 함수 호출을 줄이기 위해 dp[n][r] 배열을 선언하고 메모이제이션을 했습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
1010_다리 놓기
1116KB	0ms
*/
#include <cstdio>

const int LM = 30;
int dp[LM][LM];
int T, N, M;

int bin(int n, int r) {
	if (!dp[n][r]) {
		if (n == r || r == 0) dp[n][r] = 1;
		else dp[n][r] = bin(n - 1, r - 1) + bin(n - 1, r);
	}
	return dp[n][r];
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &T);
	while (T--) {
		scanf("%d %d", &N, &M);
		printf("%d\n", bin(M, N));
	}
	return 0;
}