[BaekJoon/C] No.1010 : 다리 놓기

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

No.1010 문제

 

문제해석

 

1. 입력받을 변수 : T(개의 테스트) / N(서쪽에 위치한 사이트) / M(동쪽에 위치한 사이트)
2. 조합을 이용하여 문제를 풀어줍니다.
   • 동쪽에서 서쪽의 사이트수인 4개의 사이트를 뽑고 서쪽에서 가장 위에 있는 1번 사이트를 동쪽에서 뽑은 사이트 중 가장 위에 있는 사이트와 연결, 서쪽 2번 사이트를 동쪽에서 두번째로 위에 있는 사이트와 연결하면서 앞서 말한 과정을 총 4번 반복하면 겹치지 않으면서 다리를 모두 연결할 수 있습니다.
   • 이때 사이트를 뽑을 때 조합이 필요합니다.
   • M개 중 N개를 선택 => C(M,N)= M! / N!(M−N)! : 분자를 먼저 계산한 결과값을 분모의 식으로 나누어줍니다. 
     

     

     ​

for (int j = 0; j < N; j++) {
    bridge *= M - j; // bridge*(M-j)
    bridge /= 1 + j; // bridge÷(1+j)
}

 

소스코드 & 문제풀이

 

#include <stdio.h>

int main() {
	int T, N, M, bridge;
	scanf("%d", &T); // 테스트 할 개수를 입력받습니다
	
	for (int i = 0; i < T; i++) { 

		bridge = 1; // T번의 반복을 한번 실행할 때마다 다리를 1로 초기화 시켜줍니다
		scanf("%d %d", &N, &M); // 서쪽과 동쪽 사이트의 개수를 입력받습니다
		for (int j = 0; j < N; j++) { // M개 중 N개를 선택하는 조합을 사용합니다
			bridge *= M - j;
			bridge /= 1+ j;
		}
		
		printf("%d\n", bridge); // 다리를 지을 수 있는 경우의 수를 출력합니다

	}

}

 

 

예제 입출력 결과