[C++] 백준(BOJ) | 1010번 : 다리 놓기

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

1010번: 다리 놓기

 

 

이 문제는 보자마자 조합 문제라는게 읽혀져 크게 어렵진 않았다.

하지만 함수를 만드는데 자꾸 오류가 떴었음 ..

 

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

// nCr = n-1Cr-1 + n-1Cr
int T, N, M;
long long dp[35][35];

long long combination(int n, int r) {
    if ((n==r) || (r==0))
        return 1;
    
    if (dp[n][r] != 0)
        return dp[n][r];

    dp[n][r] = combination(n-1, r-1) + combination(n-1, r);

    return dp[n][r];
}

int main() {

    cin >> T;

    while(T--) {
        
        cin >> N >> M;

        cout << combination(M, N) << '\n';
    }

    return 0;

}

 

마지막에 combination(N, M)이라고 썼어서 오류가 떴었다 바보

 

int가 아니라 long으로 쓰는 것도 주의하자

 

 

---

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

// nCr = n-1Cr-1 + n-1Cr
int T, N, M;

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

int main() {

    cin >> T;

    while(T--) {
        
        cin >> N >> M;

        cout << combination(M, N) << '\n';
    }

    return 0;

}

 

참고로 따로 dp 배열을 만들지 않고 그대로 return하면 시간초과가 떴다.