[Baekjoon] 9084번: 동전

 

 

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

9084번: 동전

 

---

 

문제 해결 과정

착안

문제에서 주어진 서로 다른 $n$ 가지 동전의 가치를 $c_1, c_2, \cdots, c_n$, 특정한 금액 $m$을 만들기 위한 경우의 수는

 

1) $c_1$ 짜리 동전만 사용하여 만드는 경우 (가능하다면)

2) $c_2$ 짜리 동전을 추가로 사용하여 만드는 경우  (가능하다면)

3) $c_3$ 짜리 동전을 추가로 사용하여 만드는 경우  (가능하다면)

$\cdots$

 

등을 모두 합한 값이다. 이러한 계산은 특정 공식이 존재해 단번에 계산할 수 있는 계산이 아니므로, 각각의 동전을 추가적으로 사용해 금액을 만들 수 있는 경우의 수를 동적계획법(dynamic programming)을 활용해 누적시켜가며 계산하고자 하였다.

 

구현

편의상, 주어지는 서로 다른 가치의 $n$ 개의 동전을 $c_i \space (1 \le i \le n)$, 경우의 수를 저장할 배열을 Price[] 라고 하자. 이때, Price[] 배열은 Price[0] = 1 (이유는 아래 참고)을 제외한 나머지 요소의 값을 0으로 초기화 한다.

 

$i$ 번째 동전에 대해, 해당 동전을 추가적으로 사용할 때 누적되는 경우의 수를 누적 계산하기 위해, 낮은 금액부터 순차적으로 아래와 같이 계산하면 경우의 수를 누적 계산할 수 있다.

Price[$m$] += Price[$m - c_i$];   (단, $m - c_i \ge 0$)

이때, $m - c_i = 0$ 인 경우는 만들고자 하는 금액이 동전의 가치와 같은 경우이므로 Price[0] = 1 이어야 한다. 한편, 동전에 대한 반복문과 금액에 대한 반복문을 중첩하여 이중 반복문을 구현할 때, 반복문 순서에 주의하면 위의 방법을 통해 문제를 해결할 수 있다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		int N, M, Price[10001] = { 1, };
		cin >> N;

		vector<int> Coins(N);
		for (int i = 0; i < N; i++)
			cin >> Coins[i];

		cin >> M;
		for (int coin : Coins)
			for (int i = 0; i <= M; i++)
				if (i - coin >= 0)
					Price[i] += Price[i - coin];

		cout << Price[M] << "\n";
	}

	return 0;
}

 

실행 결과