Today's Algorithm(2019-03-10)

한동안 프로그래머스에서 알고리즘 문제를 계속 풀어왔는데요. 하지만 제가 취약한 탐욕법, 다이나믹 프로그래밍을 좀 더 연습하고 싶어서 다시 백준으로 돌아왔습니다. 그 벽을 언제 넘을 수 있을지 모르겠지만 천천히 그리고 꾸준히 해보려 합니다.

 

baekjoon 1010. 다리 놓기

이 문제를 보면 결국 조합을 구하는 문제라는 것을 알 수 있을 것입니다. n과 m을 입력으로 받을 때 nCm 을 구하면 되는 것이죠. 예전에 이것을 풀기 위해선 팩토리얼을 이용하여 n! / (n-m)! * m! 로 풀어서 쓸 수 있다는 것도 기억할 것이라 생각합니다.

 

근데 그냥 이렇게 풀면 다이나믹 프로그래밍이 아니죠. 최대한 효율적으로 풀어야 하는데 그 방법은 메모입니다. 이전에 팩토리얼 수가 17를 구한게 있다면 이후에 17 밑으로는 계산해서는 안됩니다. 그것을 이용해야 하는 것이죠. 그렇기 때문에 팩토리얼 메서드를 돌릴 때 일단 이전에 계산한 것이 있는 것을 확인하고 없으면 계산한다음 다음을 위해 기록해두는 식으로 계산을 해야합니다.

 

그런데 이렇게만 하면 아직 통과하기 힘듭니다. 왜냐하면 예를들어 27 C 25 라는 조합이 있을 때 우리는 저렇게 구하는게 아니라 27 C 2로 바꾸어서 계산하잖아요. 그런식으로 N - C 가 C보다 작을 때는 C를 N - C로 바꾸어서 계산하는 것이 훨씬 효율적입니다!

 

package b1010;

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

public class Main {
    static long[] nums = new long[30];

    static {
        nums[1] = 1;
        nums[2] = 2;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            int[] arr = toArray(br.readLine());
            int N = arr[1];
            int M = arr[0];
            if (N == M) {
                System.out.println(1);
                continue;
            }
            if(N - M < M) M = N - M;
            long num = upperPart(N, M) / factoryMethod(M);
            System.out.println(num);
        }
    }

    public static long upperPart(int n, int i) {
        long num = 1;
        for (int j = 0; j < i; j++) {
            num *= n;
            n--;
        }
        return num;
    }

    private static int[] toArray(String readLine) {
        String[] arr = readLine.split(" ");
        return new int[]{Integer.parseInt(arr[0]), Integer.parseInt(arr[1])};
    }

    public static long factoryMethod(int n) {
        if (nums[n] > 0) return nums[n];
        nums[n] = n * factoryMethod(n - 1);
        return nums[n];
    }
}

46 ~ 50째 줄에 있는 팩토리얼 메서드를 보면 기록과 동시에 재귀를 통해 수를 구하고 있는 것을 볼 수 있습니다. 그리고 26번째 줄에서 N - M으로 계산하는 것이 더 유리할 때는 M을 N - M으로 바꾸고 있습니다.