백준-2294-동전 2

문제

동전 2

풀이

1. 문제조건 해석

   k를 달성하는 데 필요한 최소한의 동전 수를 구한다.

   고난이도 DP문제이다. 나는 어려워서 BFS로 풀었다.(시간 복잡도 높음)

2. 알고리즘

   • BFS의 경우 $O(NNN)$ 의 시간복잡도를 가진다 (정확하지 않음)
     • memoization으로 최적화해서 통과한 듯.
   • DP로 풀면 $O(N*K)$의 시간복잡도를 가진다.
     • dp[k] : k값을 달성하는 데 필요한 최소한의 동전 수

     • # 점화식
       dp[k] = min(dp[k], dp[k-coin[n]]+1)
       

     • DP 방법 참고 블로그
   • 재귀로 푸는 방법

3. 코드

    ###### BFS ######
    from sys import stdin
    input = stdin.readline
    n, k = [int(x) for x in input().rstrip().split()]
    coins = set()
    for _ in range(n):
        tmp = int(input().rstrip())
        if tmp <= k:
            coins.add(tmp)
    from collections import deque
    coins = sorted(list(coins), reverse=True)
    queue = deque(coins)
    visited = set()
    visited.update(coins)
    cnt = 0
    success = False
    while queue and not success:
        cnt += 1
        for i in range(len(queue)):
            cost = queue.popleft()
            if cost == k:
                success = True
                queue = None
                break
            for c in coins:
                if cost+c <= k and cost+c not in visited:
                    visited.add(cost+c)
                    queue.append(cost+c)
           
    if success:
        print(cnt)
    else:
        print(-1)
   

4. 배운점

   • BFS로 최소경로, 최소 경우의 수 구할 수는 있으나, 시간복잡도 커진다.
   • 앞으로는 최대한 DP로 푸는 연습하자.