문제

창영이는 커피를 좋아한다. 회사에 도착한 창영이는 아침 커피를 즐기려고 한다.

회사에는 N개의 커피가 각각 하나씩 준비되어 있고, 각 커피에는 카페인 함유량 Ci가 있다.

창영이는 N개의 커피 중 몇 개를 골라 정확히 K만큼의 카페인을 섭취하려고 한다.

창영이가 정확히 K만큼의 카페인을 섭취하기 위해서는 최소 몇 개의 커피를 마셔야 할까?

# 22115
import sys
input = lambda: sys.stdin.readline().strip()

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

if k == 0:
    print("0")
    exit(0)

knapsack = [[0] * (k+1) for _ in range(n+1)]

for i in range(1, n+1):
    coff = coffee[i-1]
    if coff > k:
        break
    knapsack[i][coff] = 1
    
    for j in range(k+1):
        if j > sum(coffee[:i]):
            break
            
        if coff > j or (knapsack[i-1][j-coff] == 0 and j > coff):
            knapsack[i][j] = knapsack[i-1][j]
        else:
            value = knapsack[i-1][j-coff] + 1
            if knapsack[i-1][j] == 0:
                knapsack[i][j] = value
            else:
                knapsack[i][j] = min(knapsack[i-1][j], value)
                
min_coff = (n+1)
for i in range(1, n+1):
    if knapsack[i][k] != 0:
        min_coff = min(min_coff, knapsack[i][k])

if min_coff == (n+1):
    min_coff = -1
    
print(min_coff)

백준 22115 창영이와 커피