문제

https://www.acmicpc.net/problem/2294

소스코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":  
    n, k = map(int,input().split())
    c = [int(input()) for _ in range(n)]
    dp = [ 10001 ] * (k+1)
    dp[0] = 0
    
    for i in c:
        for j in range(i,k+1):
            dp[j] = min(dp[j],dp[j-i]+1)
    if dp[k] == 10001:
        print(-1)
    else:
        print(dp[k])

설명

동전유형이 1,3,5 이고 k가 15인 경우 동전의 최소값을 나열해보자

K=1	K=2	K=3	K=4	K=5	K=6	K=7	K=8
1	1+1	3	1+3	1+1+3	3+3	1+1+5	3+5

동전1과 마찬가지고 Bottom-Up 방식으로 최소값을 체크해준다. 헷갈렸던 점은 메모이제이션에 기록될 값은 k가 j값일 때 동전의 최소값이 저장되어 있다. 그래서 새로운 j을 계산해줄 때 (j-i)을 해주어서 이미 최소값이 기록된 곳에 1만 더해주면 그 값이 최소값이다.

예를 들어 k=6인 경우 6-3인 3인 경우에 3이 하나만 있는 값이 최소 값이다. 여기에 3을 더 해주면(+1) 그 값이 그냥 최소값이다.

최소값을 구하는 문제이기 때문에 문제에 조건으로 보여준 10000보다 큰 값으로 세팅을 해줘야 10000일 때 값을 체크해줄 수 있다😑 (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000)
초기값을 100001로 체크해주지 않으면 오류가 발생한다.(TC 다 못맞춤;;)

후기

문제에 정의된 조건을 대충 확인해서 오류가 많이 발생하였다. 문제의 조건을 차분히 읽자😢😢😢