[BaekJoon] 2624 동전 바꿔주기

1.  문제 링크

https://www.acmicpc.net/problem/2624

2.  문제

요약

• k가지 동전이 각각 $n_1$, $n_2$, ..., $n_k$개 씩 들어있습니다.
• 지폐의 금액 T, 동전의 가지 수 k, 각 동전 하나의 금액 $p_i$와 개수 $n_i$가 주어질 때, 지폐를 동전으로 교환하는 방법의 가지 수를 구하는 문제입니다.
  • 방법의 수는 $2^{31} - 1$을 초과하지 않습니다.
• 입력: 첫 번째 줄에 0보다 크고 10,000보다 작거나 같은 T가 주어지고 두 번째 줄에는 0보다 크고 100보다 작거나 같은 k가 주어지며 세 번째 줄부터 k개의 줄에는 0보다 크고 T보다 작거나 같은 $p_i$와 0보다 크고 1,000보다 작거나 같은 $n_i$가 주어집니다.
• 출력: 첫 번째 줄에 동전 교환 방법의 가지 수를 출력합니다. 방법이 없을 때는 0을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;

public class Main {
	public int getCaseNum(int target, int[][] coins) {
		Arrays.sort(coins, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				if(o1[0] - o2[0] > 0) {
					return 1;
				} else {
					return -1;
				}
			}
		});
		int[][] dp = new int[coins.length][target + 1];
		for(int i = 0; i < dp.length; i++) {
			dp[i][0] = 1;
		}
		for(int i = 1; i <= coins[0][1]; i++) {
            if(coins[0][0] * i > target) {
				break;
			}
			dp[0][coins[0][0] * i] = 1;
 		}
		for(int i = 1; i < coins.length; i++) {
			for(int j = 1; j <= target; j++) {
				for(int l = 0; l <= coins[i][1]; l++) {
					if(j - (coins[i][0] * l) < 0) {
						break;
					} else {
						dp[i][j] += dp[i - 1][j - (coins[i][0] * l)];
					}
				}
			}
		}
		return dp[coins.length - 1][target];
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int target = Integer.parseInt(br.readLine());
		int coin_type = Integer.parseInt(br.readLine());
		int[][] coins = new int[coin_type][2];
		for(int i = 0; i < coin_type; i++) {
			String[] input = br.readLine().split(" ");
			coins[i][0] = Integer.parseInt(input[0]);
			coins[i][1] = Integer.parseInt(input[1]);
		}
		br.close();
		Main m = new Main();
		bw.write(m.getCaseNum(target, coins) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 DP를 이용하여 구할 수 있는 문제입니다.
• 주어진 동전의 금액과 개수를 동전의 금액에 따라 오름차순으로 정렬하고 메모이제이션을 위한 2차원 배열 dp를 생성합니다.
• dp[$p_i$][M]는 T원에 대해서 $p_1$부터 $p_i$까지의 동전을 사용하여 M원을 만들 수 있는 가지 수를 나타냅니다.
• 각 동전에 대해 주어진 개수가 있기 때문에 $p_1$부터 $p_i$까지 사용하여 만들 수 있는 최대 금액이 존재하므로 최대 금액까지만 만들 수 있는 가지 수를 확인합니다.
• 오름차순으로 정렬되어 있는 상태에서 M원을 만드는 바로 이전 동전까지의 가지 수에 현재 동전을 이용하여 M원을 만들 수 있는 가지 수를 추가하면 되므로 아래와 같은 점화식이 나오게 됩니다.

  • dp[$p_i$][M] += dp[$p_{i - 1}$][M - $p_i$ * coin_num]

    • coin_num은 1보다 크거나 같고 $p_i$ 동전의 개수 $n_i$보다 작거나 같은 수를 의미합니다.(즉, 동전의 개수를 의미합니다.)
• 위에서 구한 점화식을 이용하여 T원을 만들 수 있는 가지 수를 구합니다.

1. 2차원 배열 coins에 동전의 금액과 동전의 개수를 넣고 coins 배열을 동전의 금액을 바탕으로 오름차순으로 정렬합니다.
2. 각 동전에 대해서 1원부터 T원까지 각 금액을 만들 수 있는 가지 수를 나타내는 2차원 배열 dp를 생성하고 각 행의 첫 번째 열의 값은 1로 초기화하며 dp의 첫 번째 행, 즉 coins의 첫 번째 동전에 대해 dp값을 초기화시킵니다.
   • 첫 번째 동전은 동전의 금액의 배수에 해당하는 가격에 대해서만 1가지씩 만들 수 있으므로 이를 이용하여 초기화합니다.
3. coins의 두 번째 동전부터 마지막 동전까지 반복문을 돌며 T원을 만들 수 있는 최종 경우의 수를 구합니다.
   1. 1원부터 T원까지 반복문을 돌며 각 금액에서 첫 번째 동전부터 해당 동전까지 사용하여 몇 가지의 경우의 수를 만들어낼 수 있는지 찾아냅니다.
      1. 해당 동전을 0개 사용하는 경우부터 모두 사용하는 경우까지 확인하면서 위의 점화식을 이용하여 각 동전의 개수에서 해당 금액을 만들어낼 수 있는 경우의 수를 구합니다.
4. 3번의 반복문이 끝난 후에 dp[$p_k$][T]의 값이 동전 교환 방법의 가지 수가 되므로 이를 출력합니다.