#1010: 다리 놓기

풀이방법

사용된 것:

조합

 

2022.05.08

몇 달 전에 푼 문제인데 정리글을 쓰지 않아 적는다.

 

동쪽에 있는 사이트들 중, 서쪽의 사이트 개수만큼을 고른다.

그럼 이제 다리를 놓을 수 있는 방법은 단 한 가지로 정해진다. 북쪽에서부터 차례대로 딱딱 연결하지 않으면 다리가 서로 겹치기 때문이다.

 

그러므로 이 문제의 답은

M개 중 순서 상관없이 N개를 뽑는 경우의 수이다.

 

중/고등학교 때 배운 조합 공식으로 풀면 된다.

 

코드

Java(2022.05.08)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
		
		int t = Integer.parseInt(br.readLine());	//테스트케이스의 수
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i<t; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());	//서쪽의 사이트 수
			int b = Integer.parseInt(st.nextToken());	//동쪽의 사이트 수
			int answer = 1;
			for(int j = 0; j<a; j++) {	//b개 중 순서 상관없이 a개를 고르는 경우의 수 계산
				answer *= b-j;
				answer /= j+1;
			}
			sb.append(answer + System.lineSeparator());
		}
		
		System.out.print(sb);

	}

}