백준 1010번 : 다리놓기

링크 : http://acmicpc.net/problem/1010

바로 조합 사용하면 될 것 같아서 자료구조 때 배웠던 재귀함수를 이용한 조합을 사용했다.

문제는 컴파일 시간. 처음에는 case의 크기만큼의 새로운 동적 할당하여 cout 하였는데 이러니까 시간 초과가 떴다. 그래서 배열에 넣지 않고 바로 값을 출력하도록 바꿨다.

그리고 case가 switch문에서의 case로 인식이 되는 것을 잊고 처음에는 컴파일 에러가 났었다. 변수 설정 조심하자.

#include<iostream>
using namespace std;

int combination(int n, int r) {
    if (n == r ) 
        return 1;
    if (r == 1)
        return n;
    else
        return combination(n - 1, r - 1) + combination(n - 1, r);
}


int main() {
    int casee;
    cin >> casee;
    int n_key = -1, m_key = -1;
    for (int i = 0; i < casee; i++) {
        cin >> n_key;
        cin >> m_key;
        int answer = combination(m_key, n_key);
        cout << answer << endl;
    }
    return 0;
}