[BOJ 2294] 동전 2 (Python)

문제링크

동전 2

풀이 전 계획 및 생각

0원부터 시작해서 메모이제이션을 이용해서 문제를 풀기로 결정했다.
문제 조건을 보면 동전의 가치가 목표 가격보다 크게 들어올 수 있고, 같은 가치의 동전이 여러 번 주어질 수 있기 때문에, set 자료형을 이용했고, 목표 가격 k보다 작거나 같은 가치를 가지는 동전은 set에 포함시켰다.
그 조건만 고려해주면 일반적인 dp문제와 마찬가지로 이전 단계에서 사용했던 결과를 가져다가 풀 수 있었다.
가장 최소 횟수를 구해주면 되기 때문에, 가치 i를 만들 수 있는 경우 중에서 가장 작은 경우만 저장해주면서 다음 단계를 진행했다.
이때, 문제에서 요구하는 가장 큰 동전의 가치가 10000이기 때문에, 메모이제이션을 위한 리스트는 10000보다 큰 값인 10001로 초기화해준 상태에서 문제를 풀었다.

풀이

import sys
from collections import deque

n , k = map(int,sys.stdin.readline().split())

dp_coin = [10001]*(k+1)
coin = set()

for _ in range(n):
    c = int(sys.stdin.readline())
    if c <= k:
        coin.add(c)
        dp_coin[c] = 1

for i in range(k+1):
    for c in coin:
        if i-c >= 0:
            dp_coin[i] = min(dp_coin[i],dp_coin[i-c]+1)
if dp_coin[k] == 10001:
    print(-1)
else:
    print(dp_coin[k])

풀이하면서 막혔던 점과 고민했던 점

크게 어려웠던 점은 없었다.

풀이 후 알게된 개념과 소감

중복 제거를 할 때는 set이 정말 강력한 무기라는 것을 다시 한 번 알 수 있었다. 리스트의 기능이 필요한 조작이 없는 경우에는 정말 편하고 빠른 것 같다.