백준 7579번 앱 (Feat. Python)

문제 설명

핸드폰의 앱이 활성화 상태로 놓여있을 때 새로운 앱을 실행하면 필요한 메모리 공간만큼 활성화 상태인 앱들을 종료해야 한다. 활성화 상태인 앱들은 다시 실행할 때 드는 비용이 각각 정해져 있을 때, 새로운 앱이 실행되는데 필요한 공간을 확보하고 이 비용을 최소로 하는 방법을 구하는 문제입니다.

아이디어

냅색 알고리즘을 사용할 수 있는 문제입니다.

냅색 알고리즘

가방 안에 넣을 수 있는 무게가 M이고 가방에 넣을 수 있는 물건들의 무게와 물건을 넣었을 때의 가치가 각각 정해져 있을 때 가방안에 물건을 넣어 만족할 수 있는 최대 가치를 구하는 알고리즘입니다.

냅색 알고리즘을 풀 때 가장 헷깔렸던 것 중 하나는 분해를 어떠한 방식으로 진행해야 하는지 입니다.

A, B, C, D 물건을 가방에 넣는다고 했을 때, 문제의 해답이 나오는 함수를 NC(ABCD, 가치 총합)로 지정했을 때 이 함수가 실행되면 탑다운 방식으로 다음 실행되어야 하는 함수를 스스로 생각해내야 합니다.

여기서 하지 말아야 하는 점은 각각의 물건을 집어넣고 빼는 행위만 생각해서는 안된다는 점입니다.

예를 들면, 위의 함수를 NC(ABC,가치 총합-{D의 가치}), NC(ACD, 가치 총합-{C의 가치}), ... 등 하나의 물건을 빼는 방식으로만 진행되면 안됩니다. 이런 방식으로 진행됐을 경우, 똑같은 가치 총합에서 어떠한 물건이 포함되지 않을 경우를 빼먹게 되기 때문입니다.

NC(ABC, 가치 총합-{D의 가치})의 경우 ABC에서 D가 포함되는 경우만 생각하고 있습니다. ABC에서 D를 포함하지 않고 ABC가 가치 합의 최대일수도 있기 때문에, 물건을 포함해서 최대값이 될 경우와 포함하지 않을 때 최대가 될 경우를 생각을 해주어야 합니다.

그러므로 위의 NC(ABCD, 가치 총합) 함수는 다음과 같이 분해될 수 있습니다.

MAX( NC(ABC, 가치 총합-D의 가치), NC(ABC, 가치 총합) ) 이러한 방식으로 모든 경우의 수를 포함시켜야 합니다.

문제 해결

• 행: i행의 경우 1~i까지의 앱을 종료할 경우라고 생각합니다.

• 열: j 비용이 들 경우 확보할 수 있는 메모리의 최대라고 생각합니다.

그러므로 dp[i][j]는 1~i까지의 앱들 중, j 비용을 지불할 경우 얻을 수 있는 메모리의 최대값이라고 이해하면 됩니다.

위의 냅색 아이디어에서 얻은 것처럼 i번째 앱을 포함하는 경우와 포함하지 않는 경우를 모두 생각해보도록 하겠습니다.

포함하는 경우: dp[i][j] = max(dp[i-1][j-c[i]] + m[i])

포함하지 않는 경우: dp[i][j] = dp[i-1][j]

포함하는 경우는 j비용에서 현재 앱의 비용 c[i]를 뺀 경우에서 현재 앱을 포함한 경우일 것입니다. 그러므로 해당 메모리 값에 현재 앱을 종료했을 때 얻을 수 있는 메모리를 포함시켜주면 됩니다. (물론 j>=c[i]인 경우만 해당됩니다.)

포함하지 않는 경우는 현재 0~i-1 앱들 중 비용 j를 들여 얻을 수 있는 메모리의 최대값입니다.

위 두 가지경우 중 최대값이 dp[i][j]값이 됩니다.

전체 코드

N, M = list(map(int, input().split()))
m = [0] + list(map(int, input().split()))
C = [0] + list(map(int, input().split()))
dp = [[0 for __ in range(sum(C)+1)] for _ in range(N+1)]
result = 100*N+1

for i in range(N+1):
    for j in range(sum(C)+1):
        dp[i][j] = dp[i-1][j]

        if j < C[i]:
            continue

        dp[i][j] = max(dp[i-1][j-C[i]]+m[i], dp[i][j])

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

print(result)

해결

이번 문제는 냅색 알고리즘을 활용할 수 있는 문제였습니다. DP 문제를 만나면 항상 고생하는만큼 다른 문제로 경험을 더 쌓아보도록 하겠습니다.