백준 1010번 다리 놓기 [JAVA]

문제 출처: https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

 

Sol)

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {

        int tc; //test case 의 수 저장할 변수
        double N, M;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        tc = Integer.parseInt(br.readLine());

        while(tc > 0){
            double numerator = 1, denominator = 1;

            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Double.parseDouble(st.nextToken());
            M = Double.parseDouble(st.nextToken());

            double i = N;
            while(i > 0){
                numerator *= M;
                i--;
                M--;
            }

            while(N > 0) {
                denominator *= N;
                N--;
            }

            System.out.printf("%.0f\n", numerator / denominator);

            tc -= 1;
        }
    }
}

 

• 풀이 방향

서쪽에 있는 사이트의 개수 N개만큼의 다리를 서로 겹치지 않게 만들어야 한다. 만일 동쪽 사이트 M개중 N개를 골랐을 경우, 겹치지 않게 하기 위한 경우의 수는 1개 밖에 없다. 서로 겹치지 않게 하기 위해서는 맨 위에서부터 차례대로 동쪽 사이트와 서쪽 사이트를 이어주는 것이다. 즉, 서로 다른 M개중 N개만 골라주면 순서는 자동으로 결정되기때문에 우리는 M Combination N 만 구현해 주면 되겠다. 단, 시간 제한이 0.5초이므로 Combination을 재귀로 구현하지 말고 for문으로 구현해야겠다.

 

• 풀이

nCr 은 n! / (n - r)! * r! 이다. 약분해주면 n * (n - 1) * (n - 2) * ... * (n - r - 1) / r! 이 된다. 

분자를 수열처럼 표현해 보면, (n - 0) * (n - 1) * ... * (n - r - 1) 이 된다. 0 부터 r - 1까지 개수가 총 r개이므로 nCr의 빠른 구현은 n을 -1 해주며 r번 곱한 수를 r! 로 나눠주면 되겠다. 이 문제에서 n은 M, r은 N이 된다. 

 

• 문제에 대한 사견

문제 상황만 빠르게 파악하면 어렵지 않은 문제였다. 다만 시간제한이 0.5초라서 Combination을 재귀보다는 for문으로 짜야했다는 주의점이 있었다.