[BaekJoon] 2293 동전 1

1.  문제 링크

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

2.  문제

요약

• n가지의 동전이 있고 각각의 동전이 나타내는 가치는 다릅니다.
• n가지의 동전을 사용하여 가치의 합이 k원이 되도록 하는 경우의 수를 구하는 문제입니다.
• 사용한 동전의 구성은 같은데 순서만 다른 것은 같은 경우로 취급합니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100보다 작거나 같은 n과 1보다 크거나 같고 10,000보다 작거나 같은 k가 주어지고 두 번째 줄부터 n개의 줄에는 100,000보다 작거나 같은 자연수인 동전의 가치들이 주어집니다.
• 출력: 첫 번째 줄에 경우의 수를 출력합니다.

3.  소스코드

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

public class Main {
	public int getNumOfCase(int objective, int[] coins) {
		int[] dp = new int[objective + 1];
		dp[0] = 1;
		for(int i = 0; i < coins.length; i++) {
			for(int j = 1; j <= objective; j++) {
				if(j >= coins[i]) {
					dp[j] = dp[j] + dp[j - coins[i]];
				}
			}
		}
		return dp[objective];
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		int coin_num = Integer.parseInt(input[0]);
		int objective = Integer.parseInt(input[1]);
		int[] coins = new int[coin_num];
		for(int i = 0; i < coin_num; i++) {
			coins[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		Main m = new Main();
		bw.write(m.getNumOfCase(objective, coins) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 DP를 이용하여 해결할 수 있습니다.
• 동전의 가지 수를 늘리면서 해당 동전 가지 수에서의 경우의 수를 메모이제이션을 하여 해결합니다.
• 문제에서 주어진 예시를 토대로 구해보면 k원일 때 처음 주어진 1원짜리 동전은 k만큼 사용하는 경우 1가지 밖에 없습니다.

	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2
5

• 다음으로 1원짜리 동전과 2원짜리 동전을 조합하여 나타낼 수 있는 경우의 수는 아래와 같습니다.

	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2	1	2	2	3	3	4	4	5	5	6
5

• k가 1인 경우에는 2원보다 작으므로 2원짜리 동전을 이용하여 1원을 나타낼 수 없습니다. 그렇기 때문에 k >= coin 일 때만 값이 변경되게 됩니다.
• k = 3 일 때를 보면 기존에 1원짜리 동전으로만 나타낼 때의 경우의 수 1이 존재합니다.
• 또한 2원짜리 동전을 사용하는 경우를 보면 k = 1일 때의 경우의 수와 같습니다. 3원을 만들 때 2원을 사용하면 1원이 남기 때문에 1원을 만드는 경우의 수와 같기 때문입니다.
• 그렇기 때문에 dp[3] = dp[3] + dp[1]이 됩니다.
• 주어진 동전의 가치를 coins라는 배열에 저장하고 목표가 k원일 때 i번째 동전까지 이용하여 k원을 표현하는 경우의 수를 dp에 저장한다고 했을 때, 이를 점화식으로 표현하면 아래와 같습니다.
  • dp[k] = dp[k] + dp[k - coins[i]] (k >= coins[i])
• 위의 점화식을 바탕으로 DP를 이용하면 아래와 같은 코드를 만들 수 있습니다.

for(int i = 0; i < coins.length; i++) {
	for(int j = 1; j <= objective; j++) {
		if(j >= coins[i]) {
			dp[j] = dp[j] + dp[j - coins[i]];
		}
	}
}

• 위 점화식을 이용하여 경우의 수를 구합니다.

1. 주어진 동전의 가치들을 coins라는 배열에 저장하고 1원부터 k원까지 각 값에서의 경우의 수를 저장하기 위한 dp 배열을 생성합니다. dp[0]은 1로 초기화해줍니다.
2. 주어진 동전들에 대해 반복문을 돌면서 해당 동전까지 사용했을 때의 경우의 수를 구합니다.
   1. 목표 가격인 1원부터 k원까지 반복문을 돌면서 만약 해당 가격이 지금 확인하고 있는 동전의 가치보다 높거나 같다면 위에서 구한 점화식을 바탕으로 경우의 수를 구합니다.
3. 2번의 반복문이 끝나고 dp[k]의 값이 k원을 만드는 전체 경우의 수가 되므로 이를 출력합니다.