[BOJ-1010][C++] 다리 놓기

문제

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

 

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

 

출력

각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

 

예제 입력 1

3
2 2
1 5
13 29

 

예제 출력 1

1
5
67863915

 

알고리즘 분류

• 수학
• 다이나믹 프로그래밍
• 조합론

 

문제 출처

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

1010번: 다리 놓기

 

---

 

문제 해결 방법

• 조합(Combination, ${}_{n}C_{k}$) 알고리즘을 DP를 이용하여 구현하는 문제였다.
  • 조합 알고리즘은 서로 다른 `n` 개의 원소를 가지는 어떤 집합에서 순서에 상관 없이 `k` 개의 원소를 선택하는 것이다.
• $_{M}C_{N}$ 을 출력시키면 이 문제를 해결할 수 있다.

			
			
			
		
int nCk(int n, int k) {
    if (dp[n][k] > 0) return dp[n][k];
    else if (k == 0 || k == n) return dp[n][k] = 1;
    else if ((0 < k) && (k < n)) return dp[n][k] = nCk(n - 1, k - 1) + nCk(n - 1, k);
    else return 0;
}

 

• 시간 제한이 0.5초로 제한되어 있는 문제이기 때문에 이 문제는 반드시 DP를 이용해서 풀어야 한다.
  • 다음과 같이 재귀 호출을 이용하여 문제를 풀 경우 시간 초과 오류가 발생한다.

			
			
			
		
int nCk(int n, int k) {
    if (k == 0 || k == n) return 1;
    else if ((0 < k) && (k < n)) return nCk(n - 1, k - 1) + nCk(n - 1, k);
    else return 0;
}

 

코드

			
			
			
		
#include <iostream>
using namespace std;
 
int dp[31][31], T, N, M;
 
int nCk(int n, int k) {
    if (dp[n][k] > 0) return dp[n][k];
    else if (k == 0 || k == n) return dp[n][k] = 1;
    else if ((0 < k) && (k < n)) return dp[n][k] = nCk(n - 1, k - 1) + nCk(n - 1, k);
    else return 0;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    for (int i = 0; i < T; i++) {
        cin >> N >> M;
        cout << nCk(M, N) << '\n';
    }
 
    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [정수론 및 조합론]
• 실버V