백준 / 동전 2 / 2294번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 동전 2 / 2294번 (골드 5단계)

문제 사이트: https://www.acmicpc.net/problem/2294

 

문제 설명

---

나의 풀이

n, k = map(int, input().split())
coin = []

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

coin.sort(reverse = True)

def solution(k, coin):
    count = 100000
    for i in range(len(coin)):
        current = 0
        current_money = k
        for j in range(i, len(coin)):
            if coin[j] <= current_money:
                current = current + (current_money // coin[j])
                current_money = current_money % coin[j]
            else:
                continue
        if count > current:
            count = current

    return count

print(solution(k, coin))

처음 이 풀이는 처음부터 큰 동전을 사용하여 동전의 조합을 찾아내는 방식이라서 큰 동전을 여러 번 사용하지 못하고, 오히려 작은 동전을 여러 번 사용하는 경우를 고려하지 못하는 수가 있다.

그리고 시간 복잡도에서 최악의 경우를 봤을 때 1억번 연산을 할 수도 있기 때문에 이 풀이는 적합하지 않다.

def solution(k, coins):
    dp = [float('inf')] * (k + 1)
    dp[0] = 0

    for coin in coins:
        for i in range(coin, k + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[k] if dp[k] != float('inf') else -1


n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]

print(solution(k, coins))

DP를 이용한 풀이다.

 

• DP 배열 초기화:
  • dp[i]를 i원을 만들기 위한 최소 동전 개수로 정의한다.
  • dp[0] = 0으로 설정하고, 초기값으로는 매우 큰 값(float('inf'))을 할당한다.
• DP 배열 갱신:
  • 모든 동전에 대해 반복하며, 해당 동전을 사용하여 각 금액 i를 만드는 데 필요한 최소 동전 개수를 갱신한다.
• 결과 출력:
  • 최종적으로 dp[k] 값이 초기값이 아닌 경우 해당 값이 최소 동전 개수이다. 그렇지 않으면 -1을 출력한다.

 

---

※ 알아야 할 것

https://newkimjiwon.tistory.com/53

탐욕(그리디) 알고리즘(Greedy algorithm)

https://newkimjiwon.tistory.com/175

동적계획법(Dynamic Programming)