다리놓기 · EunJu-Kang

백준 [1010] 다리 놓기

풀이

nCr = (n!)/(r!)(n-r!) 공식을 활용하여 풀 수 있다.
처음에는 공식을 몰라서 재귀로만 풀었다가 시간초과가 발생하여 결국 공식활용하여 시간초과내에 풀 수 있었다.
해당 문제는 0.5초 이내의 시간 제한이므로 공식을 적용하거나 DP를 활용해야 하지만, DP를 활용하기 위해서도 결국 공식을 활용해야함.

주의사항 : 누적되는 result의 값이 꽤 크므로 long으로 하면 실패함

소스코드1. 공식 사용 (성공)

import java.math.BigInteger;
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 tc = 0; tc < T; tc++) {
            int N = sc.nextInt();
            int M = sc.nextInt();

            int diff = M - N;
            BigInteger result = BigInteger.ONE;
            for (int i = M; i >= 1; i--) {
                result= result.multiply(BigInteger.valueOf(i));

                if (i == diff + 1) break;
            }
            for (int j = 1; j <= N; j++) {
                result = result.divide(BigInteger.valueOf(j));
            }

            System.out.println(result);
        }
    }
}

소스코드2. 시간 초과 났던 코드 (실패)

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private static int result;

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

        int T = sc.nextInt();
        for (int tc = 0; tc < T; tc++) {
            result = 0;

            int N = sc.nextInt();
            int M = sc.nextInt();

            buildBridge(new int[N], N, M, 0, 0);
            System.out.println(result);
        }
    }

    private static void buildBridge(int[] westSite, int N, int M, int westSiteNo, int eastSiteNo) {
        if (westSiteNo == N) {
            result++;
            return;
        }

        if (eastSiteNo == M || westSiteNo > eastSiteNo) {
            return;
        }

        // 다리가 겹치는 경우
        if (westSiteNo > 0 && westSite[westSiteNo - 1] > eastSiteNo) {
            return;
        }

        // 서쪽의 일부 사이트가 다리건설이 불가능해진 경우
        if ((N - (westSiteNo + 1)) > (M - (eastSiteNo + 1))) {
            return;
        }

        westSite[westSiteNo] = eastSiteNo;
        buildBridge(westSite, N, M, westSiteNo + 1, eastSiteNo + 1);
        westSite[westSiteNo] = 0;
        buildBridge(westSite, N, M, westSiteNo, eastSiteNo + 1);
    }
}