Today's Algorithm(2019-03-15)

baekjoon2293. 동전1

이제 정말 제대로 된 다이나믹 프로그래밍 문제를 만나는 것 같습니다. 다이나믹 프로그램에서는 기록을 해두고 그것을 이용하여 푸는 것이 중요한데요. 중요한건 '어떤 것을 기록하느냐'입니다. 그건 문제에 따라 다릅니다.

 

이 문제의 경우 '경우의 수'가 구하는 것인데요. 그럼 기록하는 것도 경우의 수를 기록해놓고 그 전에 구해놓은 경우의 수를 재활용하는 방법을 생각해야합니다.

 

위 그림에서 [해결전략]에 하나의 표가 보일 것인데요. 저게 기록해두는 배열입니다. 이 문제는 이런 전략으로 기록할 것입니다.

d [i] [j] : i 번째까지 코인들로 j라는 수를 만들어 내는 경우의 수

ex) 위 경우 A(0) = 1 로 3을 만드는 경우는 1+1+1 하나 밖에 없으니까 d [1] [3] = 1이라고 기록하는 것입니다.

i번째 코인 < j : 바로 위(row - 1)의 경우의 수

i번째 코인 >= j : 바로 위의 경우의 수 + d [i] [j - 코인]

i번째 코인 < j에 대해서 위의 경우의 수 바로 받는 이유는 추가해줄 경우의 수가 없기 때문입니다. i번째 코인 >= j 에 대해서 d [i] [j - 코인] 을 더해주는 이유 그 경우의 수에 해당 코인을 더해주면 j를 만들 수 있는 또 다른 경우의 수이기 때문입니다. 예를들어 위의 그림에서 색으로 표시해둔 d [2] [4] = 3 인 이유는 다음과 같은 경우의 수여서 인데요.

1 * 4

2 * 2

2 * 1 + 1 * 2

1 * 4는 바로 위의 경우의 수이고 2 * 2와 2 * 1 + 1 * 2가 d [2] [2] 에 해당하는 경우의 수에 해당 코인만큼 더해줬는 경우이거든요. 그래서 더해주는 겁니다.

 

이제 코드로 나타내면 다음과 같습니다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] arr = toArray(br.readLine());
        int n = arr[0];
        int sum = arr[1];
        List<Integer> coins = getCoins(n, br);
        int[][] d = new int[coins.size() + 1][sum + 1];
        init(d);

        for (int row = 1; row <= coins.size(); row++) {
            int coin = coins.get(row - 1);
            for (int col = 1; col <= sum; col++) {
                if(col < coin) {
                    d[row][col] = d[row - 1][col];
                    continue;
                }
                d[row][col] = d[row - 1][col] + d[row][col - coin];
            }
        }

        System.out.println(d[coins.size()][sum]);
    }

    private static void init(int[][] d) {
        for (int i = 0; i < d.length; i++) {
            d[i][0] = 1;
        }
    }

    private static List<Integer> getCoins(int n, BufferedReader br) throws IOException {
        List<Integer> coins = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            coins.add(Integer.parseInt(br.readLine()));
        }
        Collections.sort(coins);
        return coins;
    }

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

기록해두는 배열에서 row, col의 0번째 배열의 의미도 궁금하실 수 있을 것 같은데요. 그건 계산의 일관성 때문에 두었습니다. 저렇게 안하면 맨 처음 줄 같은 경우 별도 예외처리가 필요하잖아요. 계산과정을 생각하시면 그 필요성에 대해 공감하실 수 있을 것입니다.