백준 다리 놓기(1010)

다리 놓기

1. 힌트

1) 강 동쪽에 다리를 연결할 사이트를 $N$개를 선택해야합니다. 다리끼리 겹칠 수 없기 때문에 동쪽에서 $N$개의 사이트를 골랐다면 위에 있는 사이트끼리 다리를 이어줄 수 밖에 없습니다.

2) $N$개의 다리를 어떤 순서로 짓던 간에 짓고 나서 결과가 똑같으면 같은 경우의 수입니다. 그렇기 때문에 동쪽에 있는 $M$개의 사이트 중에서 $N$개를 고르는 조합$M \choose N$($mCn$과 같은 표현입니다.)으로 경우의 수를 구할 수 있습니다.

2. 접근

1) 뒤에서부터 생각해서 문제를 풀 수 있을까?

어떻게 이었는지는 신경쓰지 않고 강 동쪽에 있는 $M$개의 사이트에서 $N$개를 골랐다고 칩시다. 그런데 다리끼리 겹칠 수 없기 때문에 어떻게 고르더라도 서쪽에서 동쪽으로 잇는 방법은 하나 뿐입니다. 바로 위에서부터 아래로 순서대로 이어주는 것이죠. 그렇기 때문에 우리가 구하고자 하는 경우의 수는 강 동쪽에서 $N$개의 사이트를 고르는 것이고, 고르는 순서는 상관 없이 고른 결과가 똑같다면 같은 경우의 수이므로 조합을 사용해줍니다.

3. 구현

$M \choose N$($mCn$과 같은 표현입니다.)은 다이나믹 프로그래밍으로도 구할 수 있지만 그냥 공식대로 계산해서 구할 수도 있습니다.
$nCr= \cfrac{nPr}{r!}$
분자를 모두 계산하고 분모로 나눠주는 식으로 하면 결과가 너무 커지므로(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);
	}
}

1) 시간 복잡도

반복문은 하나밖에 없습니다 $O(N)$입니다.

2) 테스트 케이스