[BOJ][Python][골3][7579] 앱

문제 링크

문제링크

냅색 알고리즘 공통

모든 냅색 문제의 변수는 아래와 같이 통일해서 풀겠습니다.

1. n : 물건의 갯수
2. b : 가방의 크기(채울 수 있는 최대 무게 or 채워야하는 최소 무게)
3. w : 물건의 무게
4. v : 물건의 가치(문제에 따라 최대화 or 최소화)

이 문제의 특징

본 문제에서 사용하는 정확한 의미는 아래와 같습니다.

1. n : 앱의 갯수
2. b : 비워야 하는 메모리의 크기
3. w : 각 앱의 메모리 크기
4. v : 각 앱의 비활성화 비용

이 문제의 특징은 세 가지 입니다.

1. 각 앱을 중복 선택(삭제)할 수 없다.
2. 채워야하는 최소 w가 주어진다.
3. v를 최소화해야 한다.

시간 초과 풀이

• dp[i] : i weight를 만들기 위해 필요한 최소 비용
• dp 초기화 : 최소값을 찾는 문제이기 때문에 dp[:] = INF
• dp[0] : 0 weight를 만들기 위한 비용은 0. 최소값을 찾기위해 꼭 필요!
• s : 모든 앱의 메모리의 합.
• 정답 : max(dp[b:s+1]). b weight 이상 공간을 만들었을 때 최소 비용

아래 코드를 사용하면 다음과 같은 방법으로 갱신됩니다.

for i in range(0, n): # 지울 앱의 index.
    for j in range(s, -1, -1): # 
        if j - w[i] >= 0:
            dp[j] = min(dp[j], dp[j - w[i]] + v[i])

1. i는 0일 때
   • dp[30] = min(dp[30], dp[0] + 3)에서만 갱신이 일어남
   • dp[30] = min(INF, 0+3) = 3
2. i는 1일 때
   • dp[40] = min(dp[40], dp[30]+0) = min(INF, 3) = 3
   • dp[10] = min(dp[10], dp[0]+0) = 0

dp[i]	0	1	2	3	4	5	6	7	8	9	10	11	12
초기값	0	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF
(6,3)	0						3
(2,0)	0		0+0				3		3+0
(4,3)	0		0				min(3,0+3)		3		6		6
dp[i]	0	INF	0	INF	INF	INF	3	INF	3	INF	6	INF	6

하지만 이 경우 $O(n * sum_of_memory) = O(1e2 * 1e7)$의 시간 복잡도를 가져 시간초과가 납니다.

시간초과 코드

import sys
from math import sqrt, ceil
from bisect import bisect_left, bisect_right
from operator import itemgetter
from collections import Counter, deque
from copy import deepcopy

# sys.stdin = open("input.txt", "r")

# N, Bag, Weight, Value
INF = 1e9
n, b = map(int, sys.stdin.readline().split())
w = list(map(int, sys.stdin.readline().split()))
v = list(map(int, sys.stdin.readline().split()))
s = sum(w)
dp = [INF] * (s + 1)
dp[0] = 0
for i in range(0, n):
    for j in range(s, -1, -1):
        if j - w[i] >= 0:
            dp[j] = min(dp[j], dp[j - w[i]] + v[i])

print(min(dp[b:s + 1]))

정답 풀이

$O(n * sum_of_cost)$의 시간 복잡도를 가지는 dp 풀이를 사용하면 비슷한 알고리즘으로 시간을 많이 줄일 수 있습니다.

• dp[i] = j : i만큼 비용을 지불할 때 얻을 수 있는 최대 메모리의 양
• dp[i] = max(dp[i], dp[i-v[j]]+w[j])

마지막으로 더해지는 비용이 어떤 앱을 취소함으로써 더해진 것인지 고려하는 방법을 사용합니다.

정답은 최소 메모리를 얻을 수 있는 최소 비용을 구하면 됩니다.

정답 코드

import sys
from math import sqrt, ceil
from bisect import bisect_left, bisect_right
from operator import itemgetter
from collections import Counter, deque
from copy import deepcopy

# sys.stdin = open("input.txt", "r")

# N, Bag, Weight, Value
INF = 1e9
n, b = map(int, sys.stdin.readline().split())
w = list(map(int, sys.stdin.readline().split()))
v = list(map(int, sys.stdin.readline().split()))
s = sum(v)
dp = [0] * (s + 1)
dp[0] = 0
for i in range(0, n):
    for j in range(s, -1, -1):
        if j - v[i] >= 0:
            dp[j] = max(dp[j], dp[j - v[i]] + w[i])

ans = 0
while ans < s and dp[ans] < b:
    ans += 1

print(ans)

Success Notice: 수고하셨습니다.