λ©λͺ¨λ¦¬ : 29028KB
μκ° : 320ms
import sys
input = sys.stdin.readline
def nj(k, coin, dp):
temp=[]
for i in coin:
if k >= i and dp[k-i] != -1:
temp.append(dp[k-i]+1)
if len(temp)>0:
return min(temp)
else:
return -1
n, k = map(int, input().split())
coin=[]
for i in range(n):
coin.append(int(input()))
coin.sort()
dp = [-1 for i in range(k + 1)]
for i in range(1, k+1):
if i in coin:
dp[i] = 1
else:
dp[i] = nj(i, coin, dp)
print(int(dp[k]))
coin λ°°μ΄μ μμ == dp μ μΈλ±μ€
μΈ λΆλΆμ νμ 1κ°μ΄λ―λ‘ dp[x] = 1
coin λ°°μ΄μ μμ != dp μ μΈλ±μ€
μΈ λΆλΆμ dp[x-coinμ μμλ€]+1
μ μ΅μκ°μ λ£λλ€
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
import sys
input = sys.stdin.readline
arr=[]
for i in range(n):
arr.append(int(input()))