[백준 조합] 다리놓기 1010 C++

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

1010번: 다리 놓기

---

이 문제는 이항정리 문제이다. 이항정리란 ? n개 중 r개를 순서와 상관없이 뽑는 조합을 말한다.

이항정리 특징을 사용해 문제를 풀면 아래와 같은 코드로 풀 수있다.

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> dp;

int func(int r, int c)
{
    if(dp[r][c]) return dp[r][c];
    
    dp[r][c] = func(r - 1, c) + func(r - 1, c - 1);
    return dp[r][c];
}
int main()
{
    int r, c, tcase;
    
    dp = vector<vector<int>>(31, vector<int>(31, 0));
    
    for(int i = 0; i < 30; ++i)
        dp[i][0] = dp[i][i] = 1;
    
    cin >> tcase;
    
    while(tcase--)
    {
        cin >> c >> r;
        cout << func(r, c) << endl;
    }
    
    return 0;
}

또한 조합의 특성으로 풀수 있다.

조합의 특성

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> dp;
int main()
{
    int r, c;
    int k = 1;
    int testcase = 0;
    int result = 1;
    
    cin >> testcase;
    
    while(testcase--)
    {
        result = 1;
        k = 1;
        
        cin >> c >> r;
        for(int i = r; i > r - c; --i)
        {
            result *= i;
            result /= k;
            ++k;
        }    
        cout << result << endl;
    }
    
    return 0;
}