간단 코테 연습>동전 2

문제 링크 : www.acmicpc.net/problem/2294

처음에 그리드를 이용해아 하는줄 알았지만.. 그렇게 되면 12,1,1,1로 동전 4개를 쓰게 되므로써 5,5,5 보다 동전을 1개 더 쓰게 된다.
따라서 dp를 써야한다.

동전1과 문제가 어느정도 비슷한 느낌은 있지만.. 아니다.. 조금 다름

로직 :
1,5,12를 이용하여 15를 만든다고 할 때, 각각 1,5,12의 경우로 나눌때 (1,15-1),(5,10-5),(12,15-12)가 된다.
그리고 위의 로직에 의해서.. 대충 그려보니 왜 dp를 이용해야 하는지 이해가 됨

import sys

n, k = map(int, sys.stdin.readline().split())
coin = [int(sys.stdin.readline()) for _ in range(n)]
dp = [10001] * (k+1)
dp[0] = 0

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

동전을 담을 coin배열과 동전 개수를 위해 dp배열을 만들어준다.
1. 데이터들을 1차원 배열에 담는다.
2. 최소 코인 갯수를 저장할 dp배열을 만들고 max(10001)으로 초기화시켜준다.
3. 코인 배열의 값을 가져오고
4. 그 값만큼 올리면서 for문을 돌아주는데
5. 현재 값에서 가져온 코인 값을 빼주었을 때의 코인 사용 개수에 지금 코인 개수 하나를 더한 값과 이전 코인들로만 조합했을 때 사용된 코인 개수를 비교하여 더 작