1010 : 다리 놓기 (C++)

1010번: 다리 놓기

---

DP로 풀지 않고

파스칼의 삼각형을 이용해 문제를 해결하였다.

#include<iostream>

using namespace std;

int main() {
    int C[31][31];

    fill(C[0], C[31], 1);

    for(int i = 2; i < 31; i++) {
        for(int j = 1; j < i; j++) {
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }

    int testCase;

    cin >> testCase;

    for(int i = 0; i < testCase; i++) {
        int N, M;

        cin >> N >> M;

        cout << C[M][N] << endl;
    }

    return 0;
}