-
동전 교환 관련 문제 접근 :: 마이구미알고리즘 2017. 2. 23. 12:07반응형
이번 글은 "동전 교환" 에 관한 알고리즘을 다뤄볼 것이다.
백준 알고리즘 사이트에서 알고리즘 분류에서 "동전 교환"을 볼 수 있다.
2293번 동전 1, 2294번 동전 2, 11047번 동전 0 문제를 통해 다룬다.
동전 0 - https://www.acmicpc.net/problem/11047
n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. (각각의 동전은 몇 개라도 사용할 수 있다.)
생각해볼 수 있는 방법은 각 동전에 대한 경우의 수를 누적시키는 것이다.
결과적으로 1원을 통해 ~ 10원까지 만들 수 있는 경우의 수를 만든 후, 3원을 통해 ...... + 5원을 통해 ........ 구하면된다.
예를 들어 합 10원, 동전 1원, 3원, 5원이 주어졌을 경우를 보자.
위 그림은 다음 코드의 결과를 나타낸다.
dp[0] = 1; for (int i = 0; i < n; i++) { for (int j = coin[i]; j <= k; j++) { dp[j] = dp[j] + dp[j - coin[i]]; } }
- dp[j] => 이전의 동전(i-1)을 기준으로 누적시킨 경우의 수
- dp[j - coin[i]] => 현재 동전(i)을 사용하여 만들 수 있는 경우의 수
dp[j - coin[i]] 의 경우, 이해가 가지않는다면, 다음과 같은 예를 생각해보자.
합 j 가 7원이면서 coin[i] 이 3원일 경우를 보자. => dp[7] - dp[7 - 3]
7원에서 3원을 사용하면 4원이 남는다.
단순히 4원이 아니라, 4원을 만들 수 있는 경우의 수라고 생각한다.
이것은 그대로 생각해보면, 3원을 사용해 만들 수 있는 7원의 경우의 수가 된다.
* dp[0] = 1은 합이 1원의 경우 동전 1원으로 만들 수 있는 경우, 합이 3원일 경우 동전 3원으로 만들 수 있는 경우와 같은 경우를 위함이다.
* j를 coin[i]로 시작하는 이유는 coin[i]에 해당하는 가치보다 작은 합은 구할 수가 없기 때문이다.
1원 동전을 기준으로 1원부터 10원까지 경우의 수 누적.
3원 동전을 기준으로 3원부터 10원까지 경우의 수 누적.
5원 동전을 기준으로 5원부터 10원까지 경우의 수 누적.
결론적으로 각 동전을 기준으로 주어진 가치의 합(n)까지 누적시키면서 더해가는 방식으로 풀 수 있다.
n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. (각각의 동전은 몇개라도 사용할 수 있다.)
이번에는 경우의 수가 아닌 최소의 동전 개수를 구해보자.
위 문제와 같은 흐름의 점화식을 이용하여 풀 수 있다.
각 동전을 기준으로 가치의 합(n)까지 동전의 개수를 누적시키면서 최소를 구분하면 된다.
Arrays.fill(dp, 10001); dp[0] = 0; for (int i = 0; i < n; i++) { for (int j = coin[i]; j <= k; j++) { dp[j] = Math.min(dp[j], dp[j - coin[i]] + 1); } }
j - coin[i] 의 값이 0일 경우는 현재 타겟으로 하고 있는 동전의 가치와 합이 같다는 것이다.
예를 들어, j = 3, i = 2 일 경우를 생각하면 된다.
min(dp[3] = 1, dp[3 - 3] = 0 + 1)
그로인해, +1의 의미는 가치가 coin[i]인 동전을 1개 더한다는 것이다.
주어지는 각 동전의 가치를 기준으로 점화식을 접근한 방식이다.
참고 URL
http://m.blog.naver.com/occidere/220794872664
백준 알고리즘 2293번 동전 1
https://github.com/hotehrud/acmicpc/blob/master/algorithm/dp/2293.java
백준 알고리즘 2294번 동전 2
https://github.com/hotehrud/acmicpc/blob/master/algorithm/dp/2294.java
반응형'알고리즘' 카테고리의 다른 글
연쇄 행렬 곱셈 (Matrix chain multiplication) :: 마이구미 (1) 2017.11.27 디스조인트-셋(disjoint-set) :: 마이구미 (0) 2017.11.05 LCS(최장 공통 부분 수열) 알고리즘 :: 마이구미 (0) 2017.02.17 효욜적인 약수 개수 구하기 알고리즘 :: 마이구미 (2) 2017.02.09 그리디(Greedy) 알고리즘 :: 마이구미 (0) 2017.02.08