[백준 2293] 동전 1

문제 링크 : https://www.acmicpc.net/problem/2293

2293번: 동전 1

당연히 모든 경우의 수를 정말 탐색하면 시간 초과가 난다.

 

그래서 동적 계획법으로 문제를 해결하기로 했다.

 

동적 계획법에 있어서 가장 중요한 것은 점화식의 기준이 되는 변수를 잡는 것이다.

 

이 문제에서는 특이하게 기준 되는 변수가 동전의 개수가 아니라 금액이다.

 

예시를 통해 알아보자

 

---

 

3개의 동전 1,2,5원을 사용해서 5원을 만드는 경우를 보자

 

5원을 세가지 동전으로 구성하는 것이 아니라

 

세 가지 동전 중 하나를 추가해 가면서 5원까지 쌓아간다고 생각한다면

 

1. 4원까지의 구성에 1원짜리 동전을 추가하는 경우

 

2. 3원까지의 구성에 2원짜리 동전을 추가하는 경우

 

3. 0원까지의 구성에 5원짜리 동전을 추가하는 경우

 

세 가지 경우를 생각할 수 있다.

 

따라서 $k$원을 모으는 방법은

 

$$\sum_{i=1}^{n} dp [k-coin [i]]$$

 

---

 

물론 문제에서 순서만 다르고 구성이 같은 방법은

 

동일하다고 가정하기 때문에 위의 점화식이 완전하지는 않다.

 

1번에서 4까지 모으는 구성이 1,1,2이고

 

2번에서 3까지 모으는 구성이 1,1,1이라면

 

두 경우로 만들어지는 5는 1,1,1,2로 구성되기 때문에 같은 경우를 두 번 세게 된다.

 

이는 위 점화식으로 k=3일 때까지만 쌓아도 확인할 수 있다.

 

ex)

 

k = 1

 

1

 

k = 2

 

1,1

2

 

k = 3

 

1,1,1

2,1

1,2

---

 

이를 해결하기 위해서 다음과 같은 방법을 생각해냈다.

 

마지막으로 추가한 동전보다 더 작은 가치의 동전은 새로 추가할 수 없다.

 

k=3에서 기존에 k=2에서 있던 하나의 2원짜리에 1원을 추가할 수 없게 하는 것이다.

 

2, 1

 

즉, 구성되는 금액에서 동전들이 오름차순으로 정렬되게 됨으로써

 

똑같은 구성에서 순서만 바뀌는 상황을 고려할 필요가 없게 된다.

 

ex) k = 5

 

1,1,1,1,1

1,1,1,2

1,2,2

5

---

 

코드상에서 구현하기 위해서는 동전을 기준으로 반복문을 돌면 된다.

 

1번째 동전으로 구성할 수 있는 모든 경우를 구하고

 

뒤에 2번째 동전을 몇개 추가해서 구성할 수 있는 모든 경우를 더하고

 

뒤에 3번째 동전을 몇개 추가해서 구성할 수 있는 모든 경우를 더하고

 

...

 

예시에서는 1원으로 구성할 수 있는 경우를 먼저 구한다.

DP[1] = 1 (1)
DP[2] = 1 (11)
DP[3] = 1 (111)
DP[4] = 1 (1111)
DP[5] = 1 (11111)

다음으로 2원을 몇개 추가해서 구성할 수 있는 경우를 더해준다.

DP[1] = 1 (1)
DP[2] = 1+1 (11,2)
DP[3] = 1+DP[1] = 2 (111,12)
DP[4] = 1+DP[2] = 3 (1111,112,22)
DP[5] = 1+DP[3] = 3 (11111,1112,122)

마지막으로 5원을 추가해서 구성할 수 있는 경우도 더해준다.

DP[1] = 1 (1)
DP[2] = 2 (11,2)
DP[3] = 2 (111,12)
DP[4] = 3 (1111,112,22)
DP[5] = 3+1 = 4 (11111,1112,122,5)

 

---

 

#include <iostream>
#include <algorithm>
using namespace std;

int n, k;
int dp[10005];
int value[1005];
int main(void) {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		scanf("%d", &value[i]);
	}
	//sort(value, value + n);

	dp[0] = 1;
	for (int j = 0; j < n; j++) {
		for (int i = 0; i <= k; i++) {
			if (i - value[j] >= 0) {
				dp[i] += dp[i - value[j]];
			}
		}
	}

	cout << dp[k] << endl;
	return 0;
}

사실 잘 생각해보면 동전을 정렬할 필요도 없다

 

똑같은 종류의 동전이 여기저기서 튀어나오지 않고

 

뭉쳐 있도록 하면 중복은 처리할 수 있다

 

1 2 1 2 2 (X)

 

2 2 2 1 1 (O)