• 동전 교환 관련 문제 접근 :: 마이구미
    알고리즘 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원이 주어졌을 경우를 보자.


    백준 11047번 동전 0



    위 그림은 다음 코드의 결과를 나타낸다.


    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

    반응형

    댓글

Designed by Tistory.