백준 7579 [python]

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

import sys

N, M = map(int, sys.stdin.readline().split())
DP_MAX_LEN = N * 100 + 1
m = list(map(int, sys.stdin.readline().split()))
c = list(map(int, sys.stdin.readline().split()))

dp = [[m[0] if i >= c[0] and j == 0 else 0 for i in range(DP_MAX_LEN)] \
for j in range(N)]
res = DP_MAX_LEN

for i in range(1, N):
    for j in range(c[i]):
        dp[i][j] = dp[i - 1][j]
    for j in range(c[i], DP_MAX_LEN):
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + m[i])
        if dp[i][j] >= M:
                res = min(res, j)
                break
            
print(res)

혼자 힘으로 풀었다. 생각을 좀 하다가 냅색 문제를 활용하니 괜찮은 풀이가 나왔다. 그런데 틀렸다. 핵심 알고리즘에는 문제가 없다고 확신했다. 어디 이상한곳에 문제가 있다고 생각했다. for문이 i = 1부터 돌아가는데, 만약 input에 앱이 한 개만 주어진다면 DP_MAX_LEN이 출력된다. 문제 조건상 앱이 한 개만 주어지면 그 앱을 종료하면 메모리가 확보되기 때문에,
res = DP_MAX_LEN if N != 1 else c[0]로 고쳐서 제출했는데 또 틀렸다. 여기서 애를 좀 먹었는데, 문제는 for문 안의 첫 번째 for문에서 res가 업데이트되어야 할 경우에 업데이트가 되지 않는다는 점이다.

input이
2 30
30 40
0 5
일 때, 답은 0이지만 5가 출력된다. 첫 번째 for문에 res를 갱신하는 코드를 추가하면 되지만 코드가 더러워지기 때문에 다른 방식으로 바꿔서 제출했다.

import sys

N, M = map(int, sys.stdin.readline().split())
DP_MAX_LEN = N * 100 + 1
m = list(map(int, sys.stdin.readline().split()))
c = list(map(int, sys.stdin.readline().split()))

dp = [[m[0] if i >= c[0] and j == 0 else 0 for i in range(DP_MAX_LEN)] \
for j in range(N)]

for i in range(1, N):
    for j in range(c[i]):
        dp[i][j] = dp[i - 1][j]
    for j in range(c[i], DP_MAX_LEN):
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + m[i])
            
for i in range(DP_MAX_LEN):
    if dp[N - 1][i] >= M:
        print(i)
        break

공간복잡도를 최적화하기 위해 일차원 리스틀 이용해서 풀어보았다. 2293번 문제를 풀어서 도움이 되었는데, 이 문제에 똑같이 적용하면 방금 dp를 적용한 단계에서 중복해서 dp를 갱신하기 때문에 틀린다. 이를 해결하기 위해 구글링 해보았더니 뒤에서부터 dp 리스트를 갱신하면 된다고 한다.

import sys

N, M = map(int, sys.stdin.readline().split())
DP_MAX_LEN = N * 100 + 1
m = list(map(int, sys.stdin.readline().split()))
c = list(map(int, sys.stdin.readline().split()))

dp = [m[0] if i >= c[0] else 0 for i in range(DP_MAX_LEN)]

for i in range(1, N):
    for j in reversed(range(c[i], DP_MAX_LEN)):
        dp[j] = max(dp[j], dp[j - c[i]] + m[i])
        
for i in range(DP_MAX_LEN):
    if dp[i] >= M:
        print(i)
        break

모든 input에 대한 일반화를 시킨 풀이를 내는게 어려운 것 같다. 공부를 더 열심히 하자.