[알고리즘][Python] 백준(BOJ) 2294 동전 2_파이썬

 

2294 동전 2    https://www.acmicpc.net/problem/2294

2294번: 동전 2

 

 

 

 

문제 풀기 전 공부할 것 : 다이나믹 프로그래밍

 

 

 

 

 

 

 

 

풀이 1

<내용>

BFS를 이용해서 해결하기

• 가치가 같은 동전이 여러 번 주어질 수도 있기 때문에 coins를 set으로 입력받는다.
• 사용한 동전의 최소 개수를 출력하기 때문에 check를 만들어 확인한다.
• 불가능한 경우를 위해 flag를 설정한다.
• que에 우선 주어진 동전의 종류를 넣고 하나씩 꺼내서 k와 비교를 한다.
• que에서 꺼낸 가치의 합에 coins의 coin들의 가치를 더해서 k보다 작거나 같다면 que에 넣어 위의 과정을 반복한다.

 

 

<코드>

from collections import deque
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coins = set(int(input()) for _ in range(n))
check = [0 for _ in range(k+1)]
que = deque()
for coin in coins:
    if coin > k:
        continue
    que.append([coin, 1])
    check[coin] = 1

flag = True
while que:
    val, cnt = que.popleft()
    if val == k:
        print(cnt)
        flag = False
        break
        
    for coin in coins:
        if val + coin > k:
            continue
        if check[val+coin] == 0:
            check[val+coin] = 1
            que.append([val+coin, cnt+1])
            
if flag:
    print(-1)

 

 

 

 

 

 

 

 

 

풀이 2

<내용>

DP 이용해서 해결하기

• dp를 리스트를 만든다.
• 동전의 가치가 자연수이므로 coins에 k보다 큰 동전은 넣지 않는다.
• n가지 종류의 동전에 대해서는 사용한 동전의 개수가 1이므로 dp에 저장한다.
• dp 리스트를 for문으로 돌면서 i원을 만들 때 필요한 동전의 최소 개수를 저장한다.
• i원을 만들 수 없다면 그대로 10002가 저장되어 있으므로 최종적으로 dp[k]에 10002가 저장되어 있다면 -1을 출력한다.

 

 

<코드>

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coins = []
dp = [10002 for _ in range(k+1)]
for _ in range(n):
    coin = int(input())
    if coin <= k:
        coins.append(coin)
        dp[coin] = 1
        
for i in range(k+1):
    for coin in coins:
        try:
            dp[i] = min(dp[i], dp[i-coin]+1)
        except:
            continue
            
if dp[k] == 10002:
    print(-1)
else:
    print(dp[k])

 

 

 

 

 

 

 

 

풀이 3

<내용>

• 위의 방법에서 try, except 구문을 if 구문으로 바꾸기

 

 

<코드>

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coins = []
dp = [10002 for _ in range(k+1)]
for _ in range(n):
    coin = int(input())
    if coin <= k:
        coins.append(coin)
        dp[coin] = 1
        
for i in range(k+1):
    for coin in coins:
        if i >= coin:
            dp[i] = min(dp[i], dp[i-coin]+1)
            
if dp[k] == 10002:
    print(-1)
else:
    print(dp[k])