[python3] 백준 7579 (앱 , DP)

 

우선 A,B,C,D,E 프로세스가 존재할때 메모리크기와 코스트가 존재하기 때문에 언제 최소한의 코스트를 사용하며 60이상의 메모리가 확보되는지 확인하기 위해서는 모든 경우의 수를 확인해야한다.

A	활성화	비활성화
B	활성화	비활성화
C	활성화	비활성화
D	활성화	비활성화
E	활성화	비활성화

그럼 결과적으로 2**5의 경우의 수가 존재한다. 그런데 N값이 100이므로 2**100의 경우가 존재하는데 이걸 전부 확인하는 것은 말이 안된다. 따라서 백트래킹이나, DP 처럼 쳐낼수 있는 경우를 쳐내는 방식으로 진행해야한다.

그런데 이 문제는 냅색문제처럼 무게와 가중치가 존재하는 문제이다. 따라서 냅색의 알고리즘을 활용하면 되겠다는 생각이 들었다.
냅색의 경우는 무게 제한이 있었기 때문에 dp[i][w]로 2차원배열을 이용하여 구했다.

그러나 해당 문제는 무게(비용) 제한이 존재하지 않고 최소한의 무게일때 M만큼을 확보해야한다. 따라서 비용에 대한 제한을 두어 이차원배열을 만들어 해결하면 된다.

A,B,C,D,E를 모두 제거한다고 하면 나올 수 있는 비용은 3+0+3+5+4 = 15가 된다. 따라서 15를 이차원배열의 열값으로 놓고 진행하면 된다. 

N, M = map(int, input().split())
Mem = [0] + list(map(int, input().split()))
Cost = [0] + list(map(int, input().split()))

dp = [[0 for i in range(sum(Cost)+1)] for i in range(N+1)]
answer = sum(Cost)
for i in range(1, N+1):
    for j in range(sum(Cost)+1):
        # cost 비교
        if 0 <= j - Cost[i]:
            dp[i][j] = max(dp[i-1][j-Cost[i]] + Mem[i], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

        if dp[i][j] >= M:
            answer = min(answer, j)
print(answer)