백준 13910번 파이썬 문제풀이(개업)

---

간단한 DP문제이다. 약간 웰노운이라 쉽게 풀 수 있었다. 최대 2개만 고를 수 있기 때문에 실버이지 않나 생각해본다. 이 중반복문을 돌면서 한개 뽑았을때 2개뽑았을 때 나눠서 생각하면 쉽게 풀 수 있다.

 

import sys

sys.setrecursionlimit(10000)
input = sys.stdin.readline
N, M = map(int, input().split())
w_size = list(map(int, input().split()))

dp = [1 << 30] * (N + 1)


def recur(total):
    if total < 0:
        return 10000000
    elif total == 0:
        return 0

    if dp[total] != 1 << 30:
        return dp[total]

    for i in range(M):
        dp[total] = min(dp[total], recur(total - w_size[i]) + 1)
        for j in range(i + 1, M):
            dp[total] = min(dp[total], recur(total - w_size[i] - w_size[j]) + 1)

    return dp[total]


ans = recur(N)
if ans >= 10000000:
    print(-1)
else:
    print(ans)