어떻게 이었는지는 신경쓰지 않고 강 동쪽에 있는 개의 사이트에서 개를 골랐다고 칩시다. 그런데 다리끼리 겹칠 수 없기 때문에 어떻게 고르더라도 서쪽에서 동쪽으로 잇는 방법은 하나 뿐입니다. 바로 위에서부터 아래로 순서대로 이어주는 것이죠. 그렇기 때문에 우리가 구하고자 하는 경우의 수는 강 동쪽에서 개의 사이트를 고르는 것이고, 고르는 순서는 상관 없이 고른 결과가 똑같다면 같은 경우의 수이므로 조합을 사용해줍니다.
(과 같은 표현입니다.)은 다이나믹 프로그래밍으로도 구할 수 있지만 그냥 공식대로 계산해서 구할 수도 있습니다.
분자를 모두 계산하고 분모로 나눠주는 식으로 하면 결과가 너무 커지므로(64비트 정수형도 벗어남) 분모 분자 동시에 나눠주면서 계산해줍니다.
#include <stdio.h>
int main() {
int T, N, M, r;
scanf("%d", &T);
while (T--) {
scanf("%d %d", &N, &M);
r = 1;
for (int i = 1; i <= N; i++)
r = r * (M - i + 1) / i;
printf("%d\n", r);
}
}
반복문은 하나밖에 없습니다 입니다.