7579 앱 파이썬 백준

문제)

https://www.acmicpc.net/problem/7579

7579번: 앱

 

배낭문제는 담을 수 있는 물건이 나눌 수 있냐 없냐에 따라 나눈다고 한다.

담을 수 있는 물건이 나누어질 때 (설탕 몇 g 등) : 분할가능 배낭문제

담을 수 있는 물건이 나누어 질 수 없을 때 : 0-1 배낭문제

해당문제는 0-1 배낭문제의 경우이다.

 

처음엔 dp를 만들 때 인덱스에 byte를 넣고 for문으로 돌릴려고 했는데 byte가 천만이라 

시간초과가 날 것 같아서 어찌해야 하나 고민... 그래서 재귀로 첫번째 시도를 했다.

답을 제출하니 메모리초과도 뜨고 시간초과도 뜨고... 왜 그럴까 나중에 생각해보니 재귀 안에

반복문이 있고 그 횟수는 최대 100번이라 진행중인 index를 인자로 넘겨줘도

함수호출마다 100 * 99 * 98 ... * 1 이런식의 반복문을 하다보니 엄청 큰 반복횟수가 생기게 되는 것...

ㅜㅜ

 

 

dp를 2차원으로 [i][j]라 할 때 i 인덱스는 앱, j 인덱스는 비용, 그 값은 바이트로 해결을 해야했다.

인덱스에 byte를 넣는게 뭔가 고정관념처럼 박혀있었다 비용으로 활용할 생각을 못했다.

더 작게 활용할 수 있는걸 인덱스로 넣어야했다. j 인덱스의 최대크기는 비용들의 합.

 

 

소스코드)

import sys
'''''
sys.setrecursionlimit(100000)
app, needByte = map(int, input().split())
activeAppByte = list(map(int, input().split()))
inactiveAppCost = list(map(int, input().split()))

# 바이트를 확보하기 위한 비활성화의 최소의 비용

for idx, v in enumerate(inactiveAppCost):
    if v==0:
        needByte -= activeAppByte[idx]
        activeAppByte.remove(activeAppByte[idx])
        inactiveAppCost.remove(v)

dp = [0] * (needByte+1) # index: byte, 값: cost
ans = int(1e9)

def recur(curByte, idx, curCost):
    global ans
    if curByte == needByte:
        ans = min(ans, curCost)
        return

    for i in range(idx, len(activeAppByte)):
        if activeAppByte[i] + curByte <= needByte:
            recur(curByte + activeAppByte[i], i, inactiveAppCost[i] + curCost)


recur(0, 0, 0)
print(ans)
'''

app, needByte = map(int, input().split())
activeAppByte = [0] + list(map(int, input().split()))
inactiveAppCost = [0] + list(map(int, input().split()))

# 바이트를 확보하기 위한 비활성화의 최소의 비용
s = sum(inactiveAppCost)
dp = [[0] * (s+1) for _ in range(app+1)] # [i][j] i: i개 앱 j: 비용 // 값 : 바이트
# 바이트가 값이 크니까 더 작은 비용이 인덱스자리를 차지하게 한 것.

result = 100000
for i in range(1, app+1):
    v = activeAppByte[i]
    c = inactiveAppCost[i]
    for j in range(1, s+1):
        if j < c:
            dp[i][j] = dp[i-1][j]
        else: # 같은 비용에서 더 큰 byte를 가지도록 비교
            dp[i][j] = max(dp[i-1][j-c] + v, dp[i-1][j])
        if dp[i][j] >= needByte:
            result = min(result, j) # 더 작은 비용으로 갱신


print(result)