백준 / 골드 3 / 7579 앱 / Python [냅색, 2차원 DP, BFS]

오답: N * Msum은 너무 큼

작동 안함

'''
100 현재 실행중 앱 수
10,000,000 확보해야하는 메모리 수
10,000,000 비활성화시 확보가능 메모리
100 재실행 비용

1,000,000,000

비용 최소화.
n번째 앱까지 둘러봤을 때 msum 메모리 확보에 따른 최소 비용
dp[n][msum] = min(dp[n-1][msum], dp[n-1][msum-m] + c)

고려할 점. 딱 Msum이 아니라 Msum'이상' 확보하면 됨

'''
import sys
input = sys.stdin.readline

N, Msum = map(int, input().split())
m = list(map(int, input().split()))
c = list(map(int, input().split()))

dp = [[0] * (Msum+1) for _ in range(N+1)]

for n in range(1, N+1):
    for msum in range(1, Msum+1):
        if msum < m[n]: # m 이상을 확보하고 싶다
            dp[n][msum] = dp[n-1][msum]
        else:
            dp[n][msum] = min(dp[n-1][msum], dp[n-1][msum-m[n]] + c[n])
print(dp[N][Msum])

sum(c) 도입의 아이디어

오답: csum의 범위는 1부터가 아님

import sys
input = sys.stdin.readline

N, Msum = map(int, input().split())
m = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))
Csum = sum(c)

dp = [[0] * (Csum + 1) for _ in range(N+1)]

for n in range(1, N+1):
    for csum in range(1, Csum + 1):
        if csum < c[n]:
            dp[n][csum] = dp[n-1][csum]
        else:
            dp[n][csum] = max(dp[n-1][csum], dp[n-1][csum-c[n]] + m[n])

for csum in range(1, Csum + 1):
    if dp[N][csum] >= Msum:
        print(csum)
        break

통과

'''
1,000,000,000 N * M은 너무 커서
N * sum(c)로 해야함. <= 100 * 100 * 100 = 1,000,000

비용 최소화.
dp[n][csum]: n번째 앱까지 둘러봤고 csum 비용일 때의 최대 메모리
dp[n][csum] = min(dp[n-1][csum], dp[n-1][csum-c] + m)
'''
import sys
input = sys.stdin.readline

N, Msum = map(int, input().split())
m = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))
Csum = sum(c)

dp = [[0] * (Csum + 1) for _ in range(N+1)]

for n in range(1, N+1):
    for csum in range(Csum + 1):
        if csum < c[n]:
            dp[n][csum] = dp[n-1][csum]
        else:
            dp[n][csum] = max(dp[n-1][csum], dp[n-1][csum-c[n]] + m[n])

for csum in range(Csum + 1):
    if dp[N][csum] >= Msum:
        print(csum)
        break

1차원 dp로 개선

import sys
input = sys.stdin.readline

N, Msum = map(int, input().split())
m = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))
Csum = sum(c)

dp = [0] * 10001

for n in range(1, N+1):
    for csum in range(Csum + 1):
        if csum >= c[n]:
            dp[csum] = max(dp[csum], dp[csum-c[n]] + m[n])

for csum in range(Csum + 1):
    if dp[csum] >= Msum:
        print(csum)
        break