백준 2294 동전2

2293번에서 이어서 생각 할 수 있습니다. 

http://songsunbi.tistory.com/68

2293번 문제를 표로 그릴 수 있다면, 이 문제도 표로 그려 바로 이해할 수 있습니다. 

d[x]=y

x원을 만드는데 필요한 최소 동전의 수 y

라고 하겠습니다. 이해가 안되시면 표를 봐주세요.

문제에서 주어진 3가지의 동전 1원, 5원, 12원짜리 동전으로 15원을 만드는 상황으로 설명하겠습니다.

2293과 마찬가지로 먼저 저에게 1원만 있다고 생각합니다. 

1원짜리 동전으로 1원을 만드는데 필요한 최소 동전은 1개입니다. 2원은 2개, 3원은 3개...15원은 최소 15개의 1원짜리 동전이 필요합니다. 

이를 표로 그려보면 다음과 같습니다.

	1원	2원	3원	4원	5원	6원	7원	8원	9원	10원	11원	12원	13원	14원	15원
1원	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
5원
12원

여기서 생각해야 할 점이 있습니다. 

동적 프로그래밍은 과거의 값과 비교하여 현재에서 최적을 찾는 방법입니다. 

즉, 초기 1원을 최소의 1원짜리 동전으로 만들기 위해 무언가 비교할 대상이 필요하다는 의미입니다. 

이를 위해 배열 d를 큰 수로 초기화 해줍니다. 

0원을 만들기 위해서 동전이 0개가 필요하므로 d[0]=0으로 초기화 해줍니다. 

이제 5원짜리 동전이 있다고 생각하겠습니다.

5원짜리 동전으로 1, 2, 3,  4원짜리 동전을 만드는 경우는 생각할 필요가 없습니다. 

5원짜리 동전으로 5원을 최소의 동전으로 만드는 경우를 생각하면 됩니다. 

5원을 만드는 방법은 1원짜리 동전 5개를 사용하거나, 5원짜리 동전 1개를 사용하면 됩니다. 

저희는 최소의 동전의 경우를 필요하기 때문에 5원을 만들기 위해 필요한 최소의 동전 수는 1이 됩니다.  

6원을 만드는데는 1원짜리 동전 6개를 사용하거나 5원짜리 동전 1개와 1원짜리 동전 1개를 사용할 수 있습니다. 

저희가 원하는 답은 5원짜리 동전 1개와 1원짜리 동전 1개를 사용해 총 2개의 동전을 사용하는 경우입니다. 

표로 그려보겠습니다.

	1원	2원	3원	4원	5원	6원	7원	8원	9원	10원	11원	12원	13원	14원	15원
1원	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
5원	x	x	x	x	1	2	3	4	5	2	3	4	5	6	3

 계속해서 12원이 있는 경우 표를 그려보겠습니다.

	1원	2원	3원	4원	5원	6원	7원	8원	9원	10원	11원	12원	13원	14원	15원
1원	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
5원	x	x	x	x	1	2	3	4	5	2	3	4	5	6	3
12원	x	x	x	x	x	x	x	x	x	x	x	1	2	3	3

이를 코드로 나타내 봅니다. 코드가 이해가 안되시면 2293문제의 코드를 다시 생각해보시기 바랍니다. 

#include <iostream>

using namespace std;

//d[x]=y
//x원을 만드는데 필요한 최소 동전의 수 y

int min(int x, int y)
{
	return x < y ? x : y;
}

int main()
{
	int n, k;
	int coin[101] = { 0 };
	int d[10001] = { 0 };
	cin >> n >> k;
	for (int i = 1;i <= n;i++) {
		cin >> coin[i];
	}
	for (int i = 1;i <= k;i++) {
		d[i] = 10000000;
	}

	d[0] = 0;

	for (int i = 1;i <= n;i++) {
		for (int j = coin[i];j <= k;j++) {
			d[j] = min(d[j], d[j - coin[i]] + 1);
		}
	}

	if (d[k] == 10000000) {
		cout << -1 << endl;
	}
	else {
		cout << d[k] << endl;

	}
}