[BOJ] 1010 : 다리놓기

풀이

직접 그림판에 그려가면서 경우의수를 계산한뒤 점화식을 생각해냈다.

4의경우 : (1 4):4개 (2 4):6개 (3 4):4개 (4 4):1개

5의경우 : (1 5):5개 (2 5):10개 (3 5):10개 (4 5):5개 (5 5):1개

6의경우 : (1 6):6개 (2 6):15개 (3 6):20개 (4 6):15개 (5 6):6개 (6 6):1개

코드

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


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int arr[30][30] = { 0 };
    arr[1][0] = 1;
    arr[1][1] = 1;
    for (int i = 2; i < 30; i++) {
        arr[i][0] = 1;
        for (int j = 1; j < i; j++) {
            arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1];
        }
        arr[i][i] = 1;
    }

    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        cout << arr[m][n] << '\n';
    }
    return 0;
}

Written on March 15, 2019