05.07. 동전 2 [Dynamic Programming][백준 2294]

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

2294번: 동전 2

 

Algorithm classification : Dynamic Programming

 

05.07.1. Problem

There are n types of coins. I would like to use these coins in moderation so that their value sums to k won. At the same time, we try to minimize the number of coins. Any number of coins may be used.

The composition of the coins used is the same, only the order is different.

 

05.07.2. Input limit

In the first line, n and k are given. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) The next n lines give the value of each coin. The value of a coin is a natural number less than or equal to 100,000. A coin of the same value may be given multiple times.

 

05.07.3. Output

Print the minimum number of coins used in the first line. If not possible, -1 is output.

 

05.07.4. Solution

Greedy algorithm 포스팅에서 배수관계가 아닌 동전이라면 greedy algorithm으로 해결 할 수 없다고 말씀드렸습니다. 그렇다면 일부분을 계속 파고 들어가는 greedy algorithm이 아닌 모든 경우를 고려할 수 있는 동적계획법으로 접근해야 함을 알 수 있습니다. 

int a[101], n, k, i, j;
int dp[1000000]; 

int main()
{
	scanf("%d %d", &n, &k);
	
	for(i = 0; i < 10001; i++){
		dp[i] = 1000000;
	}	
	
	for(i = 0; i < n; i++){
		scanf("%d", &a[i]);
		dp[a[i]] = 1;
		for(j = a[i]+1; j <= k; j++){
			dp[j] = min(dp[j], dp[j-a[i]] + 1);
		}
	}
	printf("%d", dp[k] == 1000000 ? -1 : dp[k]);
	
	return 0;
}

 

dp table의 size를 처음에 k값의 최댓값으로 주면 런타임 에러가 납니다.(Out of Bounds) 다시 생각해보니 dp[a[i]]에 접근해야 하는데 동전의 최댓값으로 size를 설정하는 것이 맞습니다. 초기값도 적당한 값으로 주시면 됩니다.

 

dp table의 dp[i]를 i라는 값을 구성할 수 있는 코인의 최소 수로 정의해보겠습니다. 그렇다면 a[i]로 코인 data를 입력받은 후 바로 base case로 설정해줄 수 있습니다. 해당하는 값의 코인이 있다면 그 코인 1개로 그 값을 구성하는 것이 가장 최소일테니까요. dp table을 update하는 반복문은 a[i]+1부터 시작하면 됩니다. 실제로 업데이트되는 dp table은 새롭게 입력받은 코인의 값보다 큰 값을 만드는 경우에서만 존재하기 때문이죠.(당연히 입력받은 코인 값보다 작은 값은 해당 코인으로 만들 수조차 없습니다.) 이 반복문에서 조금 더 생각하신다면 결국 

로 update될 수도 있다는 것을 깨달으실 겁니다. 아니면 dp[j+a[i]]를 계속 update해 나가셔도 됩니다. 시간복잡도는 O(nk)입니다.

 

Top-down으로 구현하는 것도 상당히 재미있으실 겁니다.

 

 temp = min(temp, DPfunction(i, j - a[n]) + 1));

dp[i][j] = temp;

 

Base case와 dp tabel을 언제 update할지 조건을 생각해보시면 됩니다.(dp table을 update하는 것은 현실적으로 j - a[n]이 0보다 크거나 같을때 가능하다는 것을 참고해주세요.) 참고로 위 식에서 DPfunction의 argument는 당연히 i와 j입니다. 위 식을 사용하여 recursive DP function을 작성하신다면 DPfunction(0, k)가 답이 됩니다.