[Baekjoon] 2293번: 동전 1

 

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

2293번: 동전 1

 

---

 

문제 해결 과정

착안

주어지는 $n$개의 동전의 가치를 편의상 각각 $c_i \space (1 \leq i \leq n)$라고 하면, 종류가 다른 동전이 하나하나 주어질 때마다 아래와 같은 원리에 의해 단계별로 사용하는 동전의 수를 늘려가면서 가치의 총 합이 $k$ 이하의 자연수가 되도록 만드는 경우의 수를 귀납적으로 구할 수 있다.

 

[전제조건]

1) 동전들을 사용하여 만들 수 있는 가치의 총 합은 1부터 $k$까지의 자연수이다. $i$번째 단계에서 $i$번째 동전이 주어졌을 때, 이러한 경우의 수를 누적하여 계산하기 위한 배열을 편의상 $DP_i[]$라고 한다. 만들 수 없는 경우는 0으로 표시한다.

2) $i$번째 단계에서, 총 $i$개의 동전을 사용하여 가치의 총 합을 1부터 $k$까지 만들기 위한 경우의 수가 $DP_i[1]$부터 $DP_i[k]$까지 누적되어 저장되어있는 상태라고 가정한다.

 

$(i+1)$번째 단계의 동전이 주어졌을 때, 만들고자 하는 가치의 총 합 $x$를 1부터 $k$까지 차례대로 누적하여 계산해보면,

 

1) $x = 1, 2, \cdots, (c_{i+1} - 1)$인 경우: $DP_{i+1}[x] = DP_{i}[x]$

$(i+1)$번째 동전을 사용할 수 없으므로 이전 단계에서 구한 경우의 수가 변하지 않는다.

 

2) $c_{i+1} \leq x < 2c_{i+1}$인 경우: $DP_{i+1}[x] = DP_{i}[x] + DP_{i+1}[x - c_{i+1}]$

$(i+1)$번째 동전을 하나만 사용할 수 있으므로, $x - c_{i+1}$만큼의 가치를 $1, 2, \cdots, i$번째 동전까지만 이용하여 만들 수 있는 경우의 수만큼 경우의 수가 늘어난다.

 

3) $2c_{i+1} \leq x < 3c_{i+1}$인 경우: $DP_{i+1}[x] = DP_{i}[x] + DP_{i+1}[x - c_{i+1}]$

$(i+1)$번째 동전을 최대 두 개 사용할 수 있으므로, $x - c_{i+1}$만큼의 가치를 $1, 2, \cdots, i, (i+1)$번째 동전을 이용하여 만드는 경우의 수만큼 경우의 수가 늘어난다.

* 참고) $(i+1)$번째의 동전을 이용하는 경우까지 포함하는 것에 유의.

 

$\cdots$ (위의 규칙성에 따라, $k$까지 반복하여 누적 계산)

 

위와 같은 과정을 동적계획법(dynamic programming)을 이용해 새로운 동전이 주어질 때마다 $x = 1, 2, \cdots, k$까지 누적하여 저장하는 과정을 반복함으로써 문제를 해결할 수 있으며, 단계 별로 서로 다른 동전이 주어지기만 한다면 동전이 주어지는 순서와는 관계 없이 항상 같은 결과를 얻을 수 있다(문제의 알고리즘 분류 부분을 참고하지 않았으면 위의 과정을 이해하고 깨닫는 데에 진짜 오래 걸렸을 것 같다...).

 

한편, 각 단계별로 $x = 1, ..., k$에 대해 순차적으로 계산만 수행한다면 동일한 배열을 계속해서 재활용할 수 있어 위의 복잡해보이는 과정을 실제로는 매우 간결한 식과 코드로 구현할 수 있다(필요 시, 아래 코드 참고).

 

구현

알고리즘을 이론적으로 이해하는 데는 다소 복잡하지만, 코드를 실제로 구현하는 것은 정말 간단하다. 단, 주의할 점은 $i$번째 단계에서 만들고자 하는 가치의 총 합이 $x = c_{i}$인 경우 $i$번째 동전을 추가적으로 이용해 가치의 총 합이 $c_{i}$가 되도록 만드는 경우의 수는 1만큼 증가하게 되는데, 이때 $x - c_{i} = 0$ 이므로 $DP[x - c_i]=DP[0]$의 값은 반드시 1이 되어야만 한다. 이 부분에 주의하고, 위의 과정들을 이해하면 코드를 쉽게 구현할 수 있다.

 

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

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int N, K;
	cin >> N >> K;
	vector<int> DP(K + 1);

	DP[0] = 1;
	while (N--)
	{
		int Coin;
		cin >> Coin;

		for (int i = Coin; i <= K; i++)
			DP[i] += DP[i - Coin];
	}

	cout << DP[K] << "\n";
	return 0;
}

 

실행 결과