백준 1010 다리 놓기

#include <cstdio>
using namespace std;
 
int d[31][31];
 
// nCr = n-1Cr + n-1Cr-1
int com(int n, int r) {
    if (d[n][r] > 0) return d[n][r];
    if (n == r || r == 0) return 1;
    else if (n < r) return 0;
    else {
        return d[n][r] = com(n - 1, r) + com(n - 1, r - 1);
    }
}
 
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, m;
        scanf("%d %d", &n, &m);
        printf("%d\n", com(m, n));
    }
    return 0;
}
 

6번 줄의 // nCr = n-1Cr + n-1Cr-1 이것을 이용하는 것이 핵심이다.

일반적인 조합의 성질인

 

이 공식을 이용하여 코드를 짜는 경우 long long int 자료형으로도 29! 을 담을 수 없으므로 불가능한 방법이다.

DP로 풀기로 했으니 그 성질을 이용하여 위와 같이 풀었다.

22번 줄의 printf("%d\n", com(m, n)); 

com을 호출할 때 인자를 바꿔서 넣어주어야 하는 것을 잊지말 것.