[백준-자바] 1010번 다리 놓기 / 2021.10.09

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

1010번: 다리 놓기

 

 

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
               int T = sc.nextInt();
               
               for(int i=0; i<T; i++) {
                   double N = sc.nextInt();
                   double M = sc.nextInt();
                   double result = 0;
                   double Number = 1;
                   for(double j=M; j>M-N; j--) {
                          Number *= j;
                      }    
                   
                      double Number2 = 1;
                      for(double k=N; k>0; k--) {
                       Number2 *= k;
                   }
                      result = Number/Number2;
                      System.out.printf("%.0f\n",result); 
           }
    }
}

풀이 : 

조합을 이용해서 푸는 문제이다. 

 

 

예를 들어 다리 3개를 겹치지않고 놓아야한다고 한다면, 강 동쪽에 있는 5개의 점중에 3개를 아무거나 뽑아서 겹치지 않도록 이어주면 된다.

 

1번 2번 4번을 뽑았을 때

2번 3번 5번을 뽑았을때

 

따라서 강 동쪽의 점 개수(M)중에서 강 서쪽의 점(N)만큼 뽑으면 된다.

조합으로 말하면 MCN이다.

 

 

조합은 위 그림과 같이 구한다. 분자는 코드에서 double Number 부분이고 분모는 double Number2 부분이다.

for문을 이용해서 구해주면된다.

 

최종적인 답은 Number/Number2인데 이것을 그대로 출력하면 출력값이 다음과 같이 나온다.

 

이 출력값들을 문제에서 원하는 출력값으로 바꿔주기 위해서는

 

System.out.printf("%0.f\n", result);  // 소수점없이 출력하기

 

라고 해주어야 문제에서 원하는 출력값이 나온다.