백준 13910번: 개업 골드 5(파이썬)

DP로 해결 가능한 문제입니다. 

 

웍은 최대 2개만 사용가능하기 떄문에 조합을 사용해서 요리 한번에 나올 수 있는 모든 경우의 수를 구해줍니다. (웍의 개수는 최대 100개 이기 떄문에 모든 조합을 구해도 시간이 크게 걸리진 않습니다.)

 

이후에는
dp[i] = min(dp[i], dp[i-num]+1) 점화식을 사용해서 1 부터 n 까지 dp를 구해주시면 됩니다. 

 

import sys, itertools

input = sys.stdin.readline

n, m = map(int, input().split())
s = list(map(int, input().split()))
s = s + list(map(sum, itertools.combinations(s, 2)))

s.sort()
INF = 1e9
dp = [INF] * (n+1)
dp[0] = 0

for i in range(1, n+1):
    for num in s:
        if num > i:
            break
        dp[i] = min(dp[i], dp[i-num] + 1)

print(dp[n]) if not dp[n] == INF else print(-1)