CC Algorithm (Coin Change)

N개의 동전을 가지고 K원을 만드는 경우의 수를 구하는 방법

 

N = 3, K = 10이며,

1원, 2원, 5원을 무한히 가지고있을때

동전을 사용하여 10원을 만드는 경우의 수를 구하는 문제이다.

단, 중복되는 경우는 제외해야한다

 

예를 들어,

3원을 만들 때

1원 + 2원 == 2원 + 1원인 경우를 의미한다.

 

처음에는 2차원 배열을 통해 구현했다

dp[N][K] 에서

N은 각 동전까지 사용했을 때 얻을 수 있는 K원의 경우의 수를 의미한다.

 

dp[0][0] = 1

0원을 만드는 경우의 수는 아무 동전도 사용하지 않을 때라고 생각하면 1가지이다.

또한, 1원까지 사용했을 때 만들 수 있는 K원의 개수 역시 1가지이다.

이를 표로 정리하면 아래와 같다.

 

N | K (i | j)	0	1	2	3	4	5	6	7	8	9	10
0 (원)	1	0	0	0	0	0	0	0	0	0	0
1 (원)	1	1	1	1	1	1	1	1	1	1	1
2 (원)
5 (원)

 

여기서 2원까지 사용했을 때를 보면,

만약 K가 2원보다 작은 경우, 즉 0과 1인 경우에 2원까지 사용한다고 하더라도 별 의미가 없다.

그렇기에 dp[2][0] = dp[1][0], dp[2][1] = dp[1][1]일 것이다.

즉, i > j 인 경우 dp[arr[i]][j] = dp[arr[i - 1]][j]라고 정의할 수 있다.

 

만약 i <= j인 경우인 2원을 살펴본다면,

2원을 만들 수 있는 경우의 수는

(1, 1), (2) 로 두 가지이다.

이는 dp[1][2] + dp[0][2]이며, 1까지 사용하여 만들 수 있는 경우의 수 + 0원에서 2원을 추가한 경우를 의미한다.

 

만약 4원을 살펴보면,

dp[2][4] = dp[1][4] + dp[2][2]라고 정의할 수 있고,

이는 1원까지 사용하여 만들 수 있는 경우의 수 + 2원에 2원을 추가한 경우를 의미한다.

그렇기에 이는

dp[arr[i]][j] = dp[arr[i - 1]][j] + dp[arr[i]][j - arr[i]]라고 정의할 수 있다.

(ex) 2원까지 썼을 때 7원을 만드는 경우 = 1원으로 7원을 만든 경우의 수 + 2원으로 5원까지 만든 경우의 수) 

이를 표로 나타내면 아래와 같다.

 

N | K	0	1	2	3	4	5	6	7	8	9	10
0 (원)	1	0	0	0	0	0	0	0	0	0	0
1 (원)	1	1	1	1	1	1	1	1	1	1	1
2 (원)	1	1	2	2	3	3	4	4	5	5	6
5 (원)	1	1	2	2	3	4	5	6	7	8	10

 

하지만 문제에서는 더 적은 메모리를 요구한다.

즉, 1차원 배열로 문제를 해결하라는 의미이다.

 

이 역시 마찬가지로 arr[i]원까지 썼을 때 만들 수 있는 j원의 경우의 수를 구하면 되지만,

이미 사용한 동전은 베이스로 깔고 더 이상 더해주지 않는 방식이다.

 

즉, 동전의 순서를 정해서

i번째 동전까지 사용한 경우의 수를 모두 구하고,

i + 1번째 동전으로 넘어가는 방식으로 구하면 된다.

 

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

 

위의 링크를 타고 들어가면 관련된 문제를 해결할 수 있다.