백준 1010번 C++

백준 1010번 다리 놓기

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

1010번: 다리 놓기

정답 코드

#include <iostream>
 
using namespace std;
 
int com(int n, int r);
int arr[31][31]={0, };
 
int main(void){
    int num;
    cin >> num;
    for(int x = 0; x < num; x++){
        int a,b;
        cin >> a >> b;
        cout << com(b, a) << endl;
    }
    
    return 0;
}
 
int com(int n,int r){
    if(arr[n][r] != 0) return arr[n][r];
    if(r == 0 || r == n) return arr[n][r] = 1;
    
    return arr[n][r] =com(n - 1, r) + com(n - 1, r - 1);
}

문제 풀이

기본적인 수학 구현 문제로써 Combination을 구현하는 문제입니다. 다만 재귀함수로 구현할 시 시간초과가 나기 때문에 dp를 이용하여서 풀었습니다.