[백준] 1010번 : 다리 놓기 (JAVA)

1. 문제 분석

 

제일 먼저 떠오르는 것은 아마도 고등학교 때 배웠던 조합이 아닐까 싶다..

 

시간복잡도 : O(N) 

알고리즘 : 조합(Combination)

2. 문제 풀이

처음에 팩토리얼 계산으로 조합을 계산했더니 long으로 자료형을 만들었음에도 오버플로우가 발생했다. 그래서 조합 계산시에 발생하는 대칭성을 이용해서 계산을 시도했다. n부터 n-k까지 k개의 수를 곱하고 1부터 k까지의 수를 나눈다. 즉, 곱셈과 나눗셈을 번갈아 가면서 하면 오버플로우가 발생하지 않을것 같다는 생각으로 풀었다.

3. 코드 작성

import java.util.Scanner;

public class BOJ_1010 {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for(int i = 0; i < T; i++){
            int N = sc.nextInt();
            int M = sc.nextInt();

            System.out.println(calc(N,M));

        }
    }

    public static long calc(int x, int y){

        int n = y - x;
        long result = 1;

        for(int i = 0; i < n; i++){
            result *= (y-i);
            result /= (i+1);
        }

        return result;
    }
}