문제

입력 , 출력

solution

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
arr = [0 for i in range(n)]
cnt = 0
for i in range(n):
    arr[i] = int(input())
arr.sort()
dp = [10001 for i in range(m + 1)]
dp[0] = 0
for i in range(n):
    for j in range(arr[i], m + 1):
        if j - arr[i] < 0:
            break
        dp[j] = min(dp[j], dp[j - arr[i]] + 1)
if dp[m] == 10001:
    print(-1)
else:
    print(dp[m])

설명

처음 접근을 그리디로 접근을 했어서 답이 틀렸었다.
dp로 풀면 간단하게 풀리는 문제였다.
dp로 현재값 - arr[i] , 10원이 현재값이면 10원 - 현재동전값이 3원 이면 7원 일때 개수 +1 아니면 10원을 전에 만들었던 값과 비교해서
min을 사용해서 더 작을것을 선택하는 방식으로 했다
마지막에 만들수 없으면 10001이 m원 값에 저장이 되어있으니
-1을 출력
아니면 dp[m] , 개수를 출력한다

후기

요새 그리디만 풀다보니 그리디로 접근을 해서 접근 자체가 틀렸던 문제다.
이제는 알고리즘 분류를 보지않고 접근을 해야겠다.