[백준] 2294 동전2

---

n개의 동전이 주어지고 최소한의 동전을 합하여 k원을 만드는 문제이다.

 

그리디, 동적 프로그래밍 두 가지 접근 방법이 가능하나, 나는 그리디 알고리즘 밖에 떠올리지 못하였다.

 

그리디

우선순위 큐를 가지고 그리디 알고리즘을 사용하면 메모리초과가 발생할 수 있다. 우선순위 큐에 들어갈 수를 직접 작성해보면 중복된 수 가 상당히 많이 삽입되기 때문에 이미 만들어진 합을 제외하면 메모리 초과를 해결 할 수 있다.

 

동적  프로그래밍

사실 이 문제는 동적 프로그래밍으로 분류되는 문제이기 때문에 그리디 풀이법이 출제자가 의도한 것은 아닐 것이다. 

 

동적 프로그래밍으로 해결하기 위해서는 점화식을 만들 수 있어야한다.

 

어떤 n 원을 만들기 위해서는 임의의 m원에서 주어진 동전 중 하나를 더해야 한다. n원을 만들기 위해 사용된 최소한의 동전 개수를 담고있는 배열을 D라고 하면 점화식은 아래와 같다.

 

n = m + coins[i]

m = n - coins[i]

 

D[n] = min(D[n], D[n - coins[i]) + 1)

소스 코드

from sys import stdin
import heapq

readline = stdin.readline


def main():
    n, k = map(int, readline().split())
    coins = [int(readline()) for _ in range(n)]    
    print(greedy_solve(k, coins))
    print(dp_solve(n, k, coins))


def dp_solve(n, k, coins):
    d = [10001] * (k+1)
    d[0] = 0
    for i in range(n):
        for j in range(coins[i], k+1):
            d[j] = min(d[j], d[j-coins[i]] + 1)

    if d[k] == 10001:
        return -1
    return d[k]

def greedy_solve(k, coins):
    pq = []
    heapq.heappush(pq, [0, k])
    visited = set()
    while pq:
        d, cur = heapq.heappop(pq)

        if cur == 0:
            return d

        for coin in coins:
            if cur - coin > 0 and cur - coin not in visited:
                heapq.heappush(pq, [d+1, cur-coin])
                visited.add(cur-coin)
            elif cur - coin == 0:
                return d + 1
    return -1

if __name__ == "__main__":
    main()