백준 9084 동전

이 문제는 동적 프로그래밍을 알아야 풀 수 있는 문제입니다. 

동적 프로그래밍은 표로 그려 머리로 이해를 해야 코드를 이해하실 수 있습니다. 

동적 프로그래밍을 잘 모르신다면, 개념을 익히시고 문제를 푸셔야 합니다.

코드를 보기 전, 설명을 보고 직접 표를 그려보시는 것을 권장합니다. 

설명하기 쉽게 10원을 3개의 2원, 3원, 5원을 이용해 몇 가지로 나타낼 수 있는지 가정하겠습니다. 

먼저 저에게 2원짜리만 있다고 가정합니다. 2원짜리만 있을 때 1~10원을 몇 가지의 방법으로 나타낼 수 있는지 표로 그려봅니다. 

2원짜리로 2원은 1가지, 4원은 2+2로 1가지, 6원은 2+2+2로 1가지..로 나타낼 수 있습니다. 이를 10원까지 생각해 표로 그려봅니다.

 

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

다음으로, 3원짜리 동전이 저에게 있다고 가정합니다. 

3원짜리 동전으로 3원은 1가지지만 6원은 2+2+2와 3+3 2가지의 경우가 존재합니다. 

여기서 동적 프로그래밍의 개념이 나옵니다. 

이전의 경우를 저장해놓고, 현재의 경우와 이전의 경우를 합해 나가면서 경우의 수를 계산합니다.

즉, 6원을 만드는 경우의 수를 계산할 때, 2원짜리로 6원을 만들 수 있는 경우의 수와 3원짜리로 6원을 만들 수 있는 경우의 수를 합해야 한다는 의미입니다. 

하나 더 고려해야 할 점이 있습니다. 3원으로 경우의 수를 계산하는데 1원과 2원의 경우를 계산할 필요가 있을까요?

어차피 제가 가지고 있는 동전은 3원이기 때문에 1원과 2원은 생각할 필요도 없게 되는 것입니다. 

표로 그려보겠습니다.

	1원	2원	3원	4원	5원	6원	7원	8원	9원	10원
2원	0	1	0	1	0	1	0	1	0	1
3원	x	x	1	1	1	2	1	2	2	2
5원

마지막으로 저에게 5원의 동전이 있다고 가정하고 표를 그려보겠습니다.

	1원	2원	3원	4원	5원	6원	7원	8원	9원	10원
2원	0	1	0	1	0	1	0	1	0	1
3원	x	x	1	1	1	2	1	2	2	2
5원	x	x	x	x	2	2	2	3	3	4

이제 개념을 알았으니 코드로 구현해 보겠습니다. 

배열의 인덱스에 주의해 주세요. 혼동이 많이 올 수 있습니다.

동전의 가짓수를 n, 2원, 3원, 5원을 담을 배열을 coin, 표를 담을 동적 배열을 d라고 선언하겠습니다.

d[10]이 아니라 d[11]로 선언한 이유는, 좀 더 직관적이기 때문입니다. 0원부터 9원이 아닌, 1원부터 10원까지로 생각하는 것이 더 편하기에 저는 11로 선언했습니다. 

동적 프로그래밍을 사용하기 위해서, 초기값 d[0]=1로 주어야 합니다.

i는 첫 번째 2원의 경우, 두 번째 3원의 경우, 세 번째 5원의 경우를 의미합니다. 

j는 2원으로 1~10원을 채우는 경우의 수, 3원으로 1~10원을 채우는 경우의 수, 5원으로 1~10원을 채우는 경우의 수를 의미합니다.  

최종적으로 저희가 원하는 4는 d[10]에 저장됩니다. 코드는 다음과 같습니다. 

#include <iostream>

using namespace std;

int main()
{
	//최대 몇 개?
	int n = 3;
	int coin[4] = { 0 };
	int d[11] = { 0 };
	coin[1] = 2;
	coin[2] = 3;
	coin[3] = 5;

	d[0] = 1;

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

	cout << d[10];
}

백준 문제 9084번 동전에 위에서 설명한 내용을 생각하며 풀어봅니다. 배열의 인덱스만 주의하시면 큰 어려움 없이 해결하실 수 있습니다. 

#include <iostream>

using namespace std;

int main()
{
	//테스트케이스 T
	int T;
	cin >> T;
	int coin[21] = { 0 };

	for (int t = 0;t < T;t++) {
		//동전의 가짓수 N
		int N;
		//만들어야 할 금액 M
		int M;
		cin >> N;

		for (int n = 1;n <= N;n++) {
			cin >> coin[n];
		}
		cin >> M;

		int d[10001] = { 0 };
		d[0] = 1;

		for (int i = 1;i <= N;i++) {
			for (int j = coin[i];j <= M;j++) {
				d[j] += d[j - coin[i]];
			}
		}
		cout << d[M] << endl;
	}

	return 0;
}