1010번: 다리 놓기

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

1010번: 다리 놓기

동쪽에 있는 M개의 사이트 중 N개의 사이트를 골라야 하고, 고르는 순서는 상관이 없으므로 주어진 문제는 조합 문제로 볼 수 있다.

N과 M의 범위가 30 이하이므로, 파스칼의 삼각형을 이용해 가능한 모든 경우를 탐색한 뒤 테스트 케이스를 진행하면 편하다.

#include <cstdio>

#define MAX_N 30
#define FOR(i, a, b) for(i = a; i < b; i++)

// tri[N][K]: 파스칼의 삼각형을 이용해 조합을 계산
int tri[MAX_N + 1][MAX_N + 1];

int main() {
    // T: 테스트 케이스의 수
    // N, M: 각각 서쪽, 동쪽의 사이트의 개수
    int T, N, M, n, k;
    
    FOR(n, 0, MAX_N) {
        // 이전 값을 탐색할 수 없는 nC0은 하드 코딩으로 초기화
        tri[n][0] = 1;
        // nCk = (n - 1)C(k - 1) + (N - 1)Ck
        FOR(k, 1, n) tri[n][k] = tri[n - 1][k - 1] + tri[n - 1][k];
    }

    scanf("%d", &T);
    while (T--) {
        // 조합을 구할 N과 M을 입력받은 뒤
        scanf("%d %d", &N, &M);
        // 해당 테스트 케이스의 컴비네이선을 출력한다
        printf("%d\n", tri[M][N]);
    }

    return 0;
}