(C++) - 백준(BOJ) 1010번 : 다리놓기

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

1010번: 다리 놓기

조합 문제였습니다.

 

풀이방법

겹치지 않게 다리를 놓는 방법은 순서에 상관없이 뽑는 조합의 방식과 유사합니다.

m개 중 n개를 뽑는 경우의 수를 출력하면 됩니다.

 

 

 

Code

#include <bits/stdc++.h>
using namespace std;
int t;
int comb[31][31];

int dfs(int n, int k){
    if(n == k || k == 0) return 1;
    int &ret = comb[n][k];
    if(ret) return ret;
    ret = dfs(n-1,k) + dfs(n-1,k-1);
    return ret; 
}

int main(){
    cin >> t;
    while(t--){
        int n, m;
        memset(comb,0,sizeof(comb));
        cin >> n >> m;
        cout << dfs(m,n) << '\n';
    }
}