https://www.acmicpc.net/problem/7579
시간 1초, 메모리 128MB
input :
- N과 M(1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000,000)
- N개의 정수, 메모리의 바이트 수인 m1, ..., mN(1 ≤ m1, ..., mN ≤ 10,000,000)
- 셋째 줄의 정수는 각 앱을 비활성화 했을 경우의 비용 c1, ..., cN(0 ≤ c1, ..., cN ≤ 100)
output :
- 메모리 M 바이트를 확보하기 위한 앱 비활성화의 최소의 비용을 계산하여 한 줄에 출력
조건 :
- N개의 앱, A1, ..., AN이 활성화
- 활성화 되어 있는 앱 A1, ..., AN 중에서 몇 개를 비활성화 하여 M 바이트 이상의 메모리를 추가로 확보해야 하는 것
- 비활성화 했을 경우의 비용 ci의 합을 최소화하여 필요한 메모리 M 바이트를 확보하는 방법
우선적으로, 그리디처럼 보였다. 그러나, 무조건 메모리가 큰 것으로 찾을 수 없기 때문에 그리디는 제껴야 한다.
그렇다고 투포인터? 할 수 없다.
고로 DP로 해야 한다.
행은 활성화되어있는 앱에 대해서, 열은 각 코스트에 대한 최대 확보 바이트를 저장해둔다.
dp[i][j] 에 j 코스트를 가지고 i번째 어플을 지울 때 어느 정도의 메모리를 확보할 수 있는지를 저장한다.
고로 dp[i - 1][j - now_cost] i - 1번째 어플을 지울 때 얻은 최대 메모리에다가 현재 삭제하는 메모리를 더해서 저장하도록 한다.
1) 행은 app 개수만큼, 열은 sum(cost)만큼 만들어준다.
2) 행을 차례대로 돌며 다음과 같은 알고리즘을 수행해준다.
3-0) 현재 앱의 cost가 j보다 클 경우 끄지 못하므로 활성화시켜둔다.
dp[i][j] = dp[i-1][j]
3-1) 그렇지 않다면 현재 앱을 끈 뒤의 byte와 그렇지 않을 경우의 byte중 큰 값을 dp에 입력한다.
dp[i][j] = max(byte + dp[i-1][j-cost], dp[i-1][j])
4) 현재 dp[i][j] 값이 M이상이라면 현재 cost, j와 이전의 result와 비교해 더 작은 값을 취해준다.
설명을 이렇게 써야 하는데..... 암트 그렇다
import sys
n, m = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))
cost = list(map(int, sys.stdin.readline().split()))
limit = sum(cost) + 1
dp = [[0] * limit for i in range(n + 1)]
ans = 999999999
for i in range(1, n + 1):
now_data, now_cost = data[i - 1], cost[i - 1]
for j in range(limit):
if j >= now_cost:
dp[i][j] = max(now_data + dp[i - 1][j - now_cost], dp[i - 1][j])
if dp[i][j] >= m:
ans = min(ans, j)
else:
dp[i][j] = dp[i - 1][j]
print(ans)
