[백준알고리즘] 2293번 동전 1 (JAVA) 문제 풀이

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.

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

2293번: 동전 1

어떻게 풀 것인가?

문제만 읽고 쉽다고 판단하면 안될 듯 하다....

다이나믹 프로그래밍 문제를 풀때는 점화식을 세우자. 이 문제의 점화식은 K >= coin[i] 일 때 dp[K] = dp[K] + dp[K - coin[i]]로 표현할 수 있다.

동전을 한가지만 사용할 때의 경우의 수, 동전을 두가지.. 세가지.. 동전을 N가지 사용할 때의 경우의 수 이런식으로 사용하는 동전의 가지 수를 늘려가면서 메모제이션을 하면된다.

먼저 1원짜리 동전만 이용하여 1원부터 k원까지 나타내는 경우의 수는 다음과 같다.

k원일 때 1원짜리 동전을 k개만큼 사용하는 1가지 경우의 수밖에 없다.

	1	2	3	4	5	6	7	8	9	10
coin[0] 1	1	1	1	1	1	1	1	1	1	1
coin[1] 2
coin[2] 5

그다음 2원짜리 동전을 조합하여 나타낼 수 있는 조합의 수는 다음과 같다.

	1	2	3	4	5	6	7	8	9	10
coin[0] 1	1	1	1	1	1	1	1	1	1	1
coin[1] 2	1	2	2	3	3	4	4	5	5	6
coin[2] 5

k = 1인 경우, 2원짜리 동전보다 작은 금액이므로 2원짜리 동전으로는 나타낼 수 없다. 

즉, k>=coin[i]일 때만 dp[k]의 값이 달라지게 된다.

자 마지막으로 5원짜리 동전으로 조합을 나타낼 경우

	1	2	3	4	5	6	7	8	9	10
coin[0] 1	1	1	1	1	1	1	1	1	1	1
coin[1] 2	1	2	2	3	3	4	4	5	5	6
coin[2] 5	1	2	2	3	4	5	6	7	8	10

k = 3일 때는 어떻게 될까?

기존에 1원짜리 동전만으로 나타냈을 때의 경우의 수는 1이었다. dp[3] = 1

3원을 만들기 위해 2원짜리 동전을 사용하는 경우는 k = 1일 때(dp[1])의 경우의 수와 같다.

k = 1일 때(dp[1])의 경우에서 2원짜리 동전만 추가하면 되기 때문이다.

 

시간복잡도

시간복잡도는 O(N x K)이다. 하지만  (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 라는 조건이 주어졌기에, 시간복잡도는 크게 고려하지않아도 괜찮다. O(N)으로 판단해도 괜찮을 듯 하다.

공간복잡도

공간복잡도 또한 O(N)으로 볼 수 있다.

 

풀면서 놓쳤던점

처음에는 DP에서 TOP-DOWN(재귀) 방식으로 풀려고 했었다.

다만 이 문제를 통해서 공부를 하다보니 Bottom-UP방식이 시간복잡도에서 훨씬 시간이 적게든다는 것을 알게되었다.

 

이 문제를 통해 얻어갈 것

다이나믹 프로그래밍에서 점화식을 세우는 법과 Bottom-up방식을 공부하였다.

내 코드 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	// 백준알고리즘 2293번 동전 1

	static int N;
	static int K;
	static int coin[];
	static int dp[];

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		coin = new int[N];
		dp = new int[K + 1];
		dp[0] = 1;

		for (int i = 0; i < N; i++) {
			coin[i] = Integer.parseInt(br.readLine());
			for (int j = 1; j <= K; j++) {
				if (j >= coin[i]) {
					dp[j] += dp[j - coin[i]];
				}
			}
		}
		System.out.println(dp[K]);

	}

}