2293 동전 1

Dynamic Programming의 전형적인 문제,

- Optimal substructure

- Memoization

 

알고리즘 문제에서, DP는 메모리와 시간을 아껴주는 도구이고

기존의 방법으로 풀기 껄끄러운 문제에 새로운 해결법을 제시해 주기도 한다.

수학적 기반은,

점화식(Recurrence relation)

 

1. 문제 파악

 

1, 2, 5가 주어질 때

10을 만들기 위해 몇 가지 조합으로 10을 만들 수 있는가.

 

1) 1원 * 10

 

2) 2원 * 5

3) 2원 * 4 + 1원 * 2

4) 2원 * 3 + 1원 * 4

5) 2원 * 2 + 1원 * 6

6) 2원 * 1 + 1원 * 8

 

7) 5원 * 2

8) 5원 * 1 + 1원 * 5

9) 5원 * 1 + 2원 * 1 + 1원 * 3

10) 5원 * 1 + 2원 * 2 + 1원 * 1

 

따라서 경우의 수는 10이다.

 

혹시, 엔터로 구분한 것에서 규칙을 발견했는가?

 

규칙은

1원을 사용한 경우,

2원을 추가로 사용한 경우,

5원을 추가로 사용한 경우

로 접근하였다는 것이다.

 

2. 아이디어

 

d[k] 을 k원을 만들 수 있는 경우의 수라고 하자.

coin[n] 안에는 n개 종류의 코인이 들어있다.

 

위의 경우 coin = {1, 2, 5}이고,

d[10] 을 찾으면 된다.

 

d[k] = d[k] + d[k - coin[n]] 가 해결방법의 핵심 아이디어 이다.

k원을 만드는 경우의 수는

i) coin[n]을 사용하지 않고 만들었던 경우의 수

ii) coin[n]을 사용하고 만드는 경우의 수

i) + ii)를 합하면 된다.

 

각 코인에 대해서

    k는 코인값부터 원하는 k값까지 차례대로 올려가며, d[k]에 memoization을 해주면 된다.

 

for each coin n 

    for each money k coin[n] to k

        d[k] = d[k] + d[k - coin[n]]

 

특별히 d[0]은 1이다.

0원의 조합을 만들 수 있는 경우의 수는 동전을 아무것도 쓰지 않는 경우 1개 이기 때문이다.

따라서 이 값을 초기화

 

 

이 표를 참고하면, 좀 더 이해가 쉬울 것이다.

첫번째 줄은 초기화 한 것,

두번째 줄은 1원만 사용,

세번째 줄은 2원을 추가로 사용,

네번째 줄은 5원을 추가로 사용한 것이다.

 

#include <cstdio>
#define MAX 10001
int d[MAX]; // d[n]는 n원을 만들 수 있는 동전의 조합 개수
int c[101]; // coins

int main() {
	int n, k;
	scanf("%d %d", &n, &k);

	for (int i = 1; i <= n; i++) {
		scanf("%d", &c[i]);
	}

	d[0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = c[i]; j <= k; j++) {
			d[j] += d[j - c[i]];
		}
	}

	printf("%d\n", d[k]);
	return 0;
}