[#1010] 다리 놓기

#include <iostream>
#include <vector>
 
using namespace std;
 
vector<vector<int>> dp(35, vector<int>(35, -1));
 
 
int findAnswer(int m, int n) {
    if (m == n || n==0) {
        dp[m][n] = 1;
        return 1;
    }
    if (n == 1) {
        dp[m][n] = m;
        return m;
    }
 
    int& ret = dp[m][n];
    if (ret != -1) 
        return ret;
 
    return ret = findAnswer(m - 1, n - 1) + findAnswer(m - 1, n);
}
 
int main() {
    int t;
    cin >> t;
 
    for (int tc = 0; tc < t; tc++) {
        int n, m;
        cin >> n >> m;
 
        //mCn
        //결국 m개에서 n개 뽑는 문제와 같다 왜냐면 순서는 뽑고 나면 정해짐
        cout << findAnswer(m, n) << "\n";
    }
 
    return 0;
}

 

이 문제는 결국 mCn 을 찾아내는 문제였다.

왜냐하면 일단 m개에서 n개를 뽑으면 다리끼리 겹쳐지지 못하므로 순서도 정해진다