[WEEK03] 백준 2294 동전 2

문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

풀이

dp[i] 를 i원을 낼 수 있는 최소동전개수라고 한다면 점화식을 이렇게 세울 수 있다.

dp[i] = min(dp[i], dp[i-k_won] + 1)

여기서 k_won은 가지고 있는 동전의 종류이다. dp[i-k_won]의 값에 k_won만 더 내면되기 때문에 +1을 해준다.

과정은 이렇다. 먼저 내야 하는 금액이 i원이라 한다면 i 크기의 리스트를 만들고 INF로 초기화 해준다.
dp[0]은 0으로 초기화 해준다. 0원은 아무것도 내지 않으면 되기때문에 0이다.

이후 가지고 있는 동전의 가지수 만큼 반복문을 돈다. 가지고 있는 동전의 단위가 k_won이라 한다면 dp[i - k_won]의 값이 INF가 아니면
dp[i] = min(dp[i], dp[i-k_won] + 1)를 해준다.

전체코드 1 (DP)

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
dp = [sys.maxsize] * (k + 1)
dp[0] = 0

for _ in range(n):
    coin = int(input())

    # 단위가 coin인 동전은 coin원 부터 낼 수 있기 때문
    # 최종금액까지 반복해준다.
    for i in range(coin, k + 1):
        if dp[i - coin] != sys.maxsize:
            dp[i] = min(dp[i], dp[i - coin] + 1)

print(dp[k] if dp[k] != sys.maxsize else -1)

두번째 방법은 BFS이다. 먼저 가지고 있는 동전을 큐에 넣어준다.
이후에 큐에서 꺼내면서 가지고 있는 동전 만큼 반복하면서 큐에서 꺼낸 값에 동전 단위를 더해주면서 더해준 값을 또 큐에 넣어주면 된다. 이때 카운트는 1씩 증가한다.

전체코드 2 (BFS)

def bfs():
    q = deque()
    coins = []

    for _ in range(n):
        tmp = int(input())
        if tmp > k: continue

        # 가치가 같은 동전 여러번 주어질 수도 있음
        if tmp not in coins:
            dp[tmp] = 1
            q.append((tmp, dp[tmp]))
            coins.append(tmp)

    coins.sort()

    while q:
        k_won, cnt = q.popleft()

        if k_won == k:
            break

        for coin in coins:
            # sort를 해줬으면 break 안해줬으면 continue
            if k_won + coin > k:
                break
            # 이미 처리했는데 또 하면 괜히 1만 증가하게 되는꼴
            if dp[k_won + coin] != 0:
                continue
            # 원래 k_won 내는법 cnt, coin 내는법 1 -> cnt + 1
            dp[k_won + coin] = cnt + 1
            q.append((k_won + coin, cnt + 1))
    
    return dp[k] if dp[k] else -1
        
n, k = map(int, input().split())
dp = [0] * (k + 1)
dp[0] = 0

print(bfs())