알고리즘

동전 교환 관련 문제 접근 :: 마이구미

mygumi 2017. 2. 23. 12:07
반응형

이번 글은 "동전 교환" 에 관한 알고리즘을 다뤄볼 것이다.

백준 알고리즘 사이트에서 알고리즘 분류에서 "동전 교환"을 볼 수 있다.

2293번 동전 1, 2294번 동전 2, 11047번 동전 0 문제를 통해 다룬다.

동전 0 - https://www.acmicpc.net/problem/11047

동전 1 - https://www.acmicpc.net/problem/2293

동전 2 - https://www.acmicpc.net/problem/2294


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

반응형