1010번 : 다리 놓기

처음에는 고3 확통때 배우는 조합 식인 을 이용하려 했으나 계산 과정에서 long long int 자료형도 담아낼 수 없는 값이 나와서 어쩔수 없이 조합 식을 dp에 적용하였습니다.

dp[i]는 i개 중 N개를 고를 때의 경우의 수입니다. 

N이 3일때,

dp[6]은  이고,

dp[7]은 입니다.

dp가 6에서 7로 변할때 4를 나누고 7을 곱한 것 처럼 dp가 i-1에서 i로 변할 때는 dp[i]=dp[i-1] * i / (i-N)가 됩니다.

따라서 각 케이스마다 dp[M]까지 테이블을 채우면 쉽게 답이 나옵니다. 이 경우에는 값이 int 자료형에 충분히 들어갑니다.

#include <stdio.h>

int dp[31];

int main() {

int T;

scanf("%d", &T);

while (T--) {

int N, M;

scanf("%d %d", &N, &M);

for (int i = 0; i <= 30; ++i) {

dp[i] = 0;

}

dp[N] = 1;

for (int i = N + 1; i <= M; ++i) {

dp[i] = dp[i - 1] * i / (i-N);

}

printf("%d\n", dp[M]);

}

}