[BOJ] 2294 - 동전 2 (Python)

 

 

아이디어 #1

 

동적 계획법으로 사용하는 동전의 최소 개수를 구한다.

 

 

풀이 #1

 

k+1로 초기화된 k+1 길이의 리스트를 dp를 생성한다.

 

차례로 입력 받은 동전의 가치 c가 k보다 크거나 중복되는 동전인 경우 continue로 건너뛰고, 아니면 dp[c]에 1을 저장한다.

c보다 큰 가치 합들에서 각각 c를 뺀 가치 합의 사용 동전 최소 개수보다 1 큰 값과 비교해 dp의 최솟값을 갱신한다.

 

가치 합을 k로 만들 수 있으면 사용하는 동전의 최소 개수를 출력하고, 그렇지 않으면 -1을 출력한다.

 

import sys

input = sys.stdin.readline

def solution():
    n, k = map(int, input().split())
    dp = [k+1]*(k+1)
    for _ in range(n):
        c = int(input())
        if c > k or dp[c] == 1:
            continue
        dp[c] = 1
        for i in range(c+1, k+1):
            dp[i] = min(dp[i], dp[i-c]+1)
    print(-1 if dp[k] > k else dp[k])

solution()

 

 

 

아이디어 #2

 

BFS로 사용하는 동전의 최소 개수를 구한다.

 

풀이 #2

 

0으로 초기화된 k+1 길이의 리스트 visited를 생성한다.

k 이하의 동전 가치들을 세트 coin에 저장하고, visited에 반영 후 queue에 동전 가치와 다음 동전 개수를 튜플로 추가한다.

 

coin을 오름차순으로 정렬된 리스트로 대체한 후 while문에서 BFS를 통해 동전으로 만들 수 있는 가치 합을 탐색한다.

k보다 큰 가치 합에 대해서는 탐색하지 않고, 가치 합으로 k를 만들면 break로 while문을 종료한다.

 

 

import sys

input = sys.stdin.readline

def solution():
    n, k = map(int, input().split())
    visited = [0]*(k+1)
    coin = set()
    queue = []
    for _ in range(n):
        c = int(input())
        if c <= k:
            coin.add(c)
            queue.append((c, 2))
            visited[c] = 1
    coin = sorted(coin)
    while queue:
        i, cnt = queue.pop(0)
        if i == k:
            break
        for c in coin:
            if i+c > k:
                break
            if visited[i+c] == 0:
                visited[i+c] = cnt
                queue.append((i+c, cnt+1))
    print(visited[k] if visited[k] else -1)

solution()