[1010] 다리 놓기

• 입력: 서쪽 다리 갯수 n, 동쪽 다리 갯수 m (n ≤ m)
• 출력: 다리가 겹쳐지지 않고 다리를 놓을 수 있는 경우의 수(int 수준)
• 알고리즘: 동적 계획법
• 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> using namespace std; vector<vector<int> > combine(30, vector<int>(30, -1)); int nck(int m, int n) { if (n == 1) return m; if (m == 1) return 1; if (m == n) return 1; if (combine[m][n] != -1) return combine[m][n]; return combine[m][n] = nck(m - 1, n) + nck(m - 1, n - 1); } int main() { int a; scanf("%d", &a); while (a--) { int m, n; scanf("%d%d", &n, &m); printf("%d\n", nck(m, n)); } return 0; }

다리를 갯수를 겹치지 않고 놓는 방법은 수학의 조합 문제와 같다. 

예를 들어 'x1≤x2이면 f(x1)≤f(x2)인 경우의 수를 구하여라'는 문제와 같다. 이 문제를 푸는 방법은 m개의 숫자 중 n개를 뽑아 크기 순서대로 놓는 것으로 mCn으로 구할 수 있다. 이 때 팩토리얼로 구하게 되면 굉장히 큰 수가 나오므로, 이항정리를 이용해야한다. 

이항정리는 nCk = n-1Ck-1 + n-1Ck이다. 이것을 이용하면 팩토리얼 없이 구할 수 있다.

• 문제 해결: https://www.acmicpc.net/problem/1010