Baekjoon-7579-앱
07 Oct 2022간단한 knapsack이었는데 문제가 한 번 꼬아져 있어서 오래 걸렸다.
memory를 넘으면서 최소 cost를 찾는 것이었는데, cost를 찾으면서 최대 memory를 찾는 문제와 동치이므로, 후자로 풀어야 한다.
전자로 풀었다가는 momory 초과
N,M = map(int, input().split())
mems = [0] + list(map(int, input().split()))
cost = [0] + list(map(int, input().split()))
cost_sum = sum(cost)
infty = int(1e4)
dp = [[0] *(N+1) for _ in range(cost_sum+1)]
for c in range(cost_sum+1):
for i in range(1,N+1):
if c-cost[i] >= 0:
dp[c][i] = max(dp[c][i-1], dp[c-cost[i]][i-1]+mems[i])
else:
dp[c][i] = dp[c][i-1]
if max(dp[c]) >= M:
print(c)
exit()