문제

풀이

  • 핵심
    • 종류로 DP를 만든다.
    • DP[K]는 K를 만들 수 있는 최소 동전 개수다.
  • 구체적인 로직
    • n,k 받기
    • arr에 array 받기
    • for i ~ n
      • dp[i][k] = min(dp[i-1][k], dp[k - arr[i]], k % i == 0 ? k / i : INF)
    • print dp[n][k]
  • 주의
    • 문제를 제대로 읽지 않아서 구할 수 없는 경우를 처리하지 못했다.
    • 코드로 옮기기 전에 조건을 다시한번 확인하자.
  • 코드
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

n,k = list(map(int, input().split()))

arr = [0,]

for _ in range(n):
    arr.append(int(input()))

INF = 1e9
dp = [[INF] * (k + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, k + 1):
        dp[i][j] = dp[i-1][j]
        if j % arr[i] == 0:
            dp[i][j] = min(dp[i][j], int(j / arr[i]))
        
        if j - arr[i] >= 0:
            dp[i][j] = min(dp[i][j], dp[i][j - arr[i]] + 1)
if dp[n][k] == INF:
    print(-1)
else:
    print(dp[n][k])