[백준] 7579. 앱 - 파이썬

[Gold III]

 

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

7579번: 앱

 

풀이

일단 보자마자 생각난 것은 "Greedy로 풀면 참 편하겠다..." 인데,

간단하게 생각해 봐도 그리디로 해결될 문제가 아님.

모든 경우의 수를 파악해봐야 될 것 같은 문제이고, DP로 풀면 되겠다 싶었다.

 

0-1 Knapsack 문제와 동일한 방법으로 풀이했다.

1 <= N <= 100, 1<= c <= 100 이기 때문에, 2차원 배열로 dp table을 모두 채워도 100 * 100^2 = 100만개 정도만 나와서 시간 내에 해결할 수 있다고 생각했음.

그리고.. 풀면서 헷갈려서 구현에 시간이 좀 걸림. Knapsack 문제를 굉장히 오랜만에 봐서 그런가, 쉽지 않았다.

다시 공부해야겠다고 느꼈음 ;ㅅ;

 

N, M = map(int, input().split())

memory = list(map(int, input().split()))
c = list(map(int, input().split()))

dp = [[0 for _ in range(sum(c)+1)] for _ in range(N+1)]

# dp[i][j] => 1~i번째 앱까지, j의 cost로 확보 가능한 메모리의 최대
for i in range(1, N+1):
    for j in range(0, sum(c)+1):
        if j >= c[i-1]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i-1]]+memory[i-1])
        else:
            dp[i][j] = dp[i-1][j]

for i, mem in enumerate(dp[N]):
    if mem >= M:
        print(i)
        break