백준 7579 - 앱

 

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

7579번: 앱

전형적인 배낭 문제 (dp 문제 유형 중 하나)라고 생각하고 풀면 된다.

 

1) dp식 정의

dp[i][j] = 1번부터 i번까지의 앱을 j의 비용을 가지고 비활성화 시켰을 때 절약할 수 있는 메모리의 최댓값

c <= 100이라고 했으므로 dp 배열의 크기는 최대 100 * 10000이 될 수 있다.

 

2) 초깃값

비용이 0이면 앱을 비활성화 할 수 없으므로 dp[i][0]은 0이다.

비활성화 비용이 0인 앱도 존재하지만, 이 문제는 점화식을 잘 설정하고 반복문을 돌리면 해결된다.

 

3) 점화식

배낭 문제의 원리는, 1부터 N번까지의 물건을 순서대로 확인하면서, i번째 물건을 선택할 경우와 포기할 경우 중 어떤 경우가 이득인지 계산하는 것이다. 이를 이 문제에 그대로 적용해보자.

 

i번째 물건(앱)을 선택(비활성화)한다고 하자. 현재 가용 비용 j에서, i번 앱은 반드시 비활성화하므로, 남은 비용은 j - cost[i]가 될 것이다. 그러면 이 비용 j-cost[i]와 i를 제외한 1부터 i-1번까지의 앱을 가지고 최대한의 이득(메모리 절약)을 봐야 한다. 그런데 이 값은 dp식 정의에 의해 dp[i-1][j-cost[i]]에 저장되어있으므로, dp[i][j]는 거기에 i번 앱을 비활성화해 절약한 메모리 mem[i]를 더한 dp[i-1][j-cost[i]] + mem[i]가 된다.

 

i번째 물건을 포기한다고 하자. i번 앱을 비활성화하지 않았으므로 비용 j가 그대로 남는다. 그 다음 위와 마찬가지로 남은 비용 j와 1부터 i-1번까지의 앱을 가지고 이득을 보면 된다. 이 값은 dp[i-1][j]에 저장되어있고, i번 앱을 비활성화하지 않았으므로 mem[i]는 더해지지 않는다. dp[i][j] = dp[i-1][j]

 

매 i와 j마다, i번 앱을 선택할 경우와 포기할 경우 중 더 이득인 경우를 찾는다.

		//포기할 경우, 	선택할 경우
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] + mem[i]);

그런데, 만약 현재 가용한 비용 j가 현재 i번 앱을 비활성화하는 비용보다 적다면 i번 앱은 비활성화가 불가능하다. 이때는 울며 겨자먹기로 dp[i-1][j]를 선택해야 한다.

if (j < cost[i])
    dp[i][j] = dp[i - 1][j];

 

 

반복문 수행을 마치면, 모든 앱을 확인한 dp[N] 배열에서 절약한 메모리(배열 원솟값)가 M 이상인 인덱스 중 최소를 찾아 반환하면 된다.

for (int i = 0; i < 10001; i++)
    if (dp[N][i] >= M)
        return i;

 

배낭 문제를 잘 이해하고 있었다면 금방 풀릴 문제였는데, 나는 멍청하게 dp식을 반대로 정의했다.

//dp[i][j] = j의 메모리를 가지고 비활성화 시켰을 때 소요되는 비용의 최솟값// 이렇게....

이렇게 풀어도 틀리지는 않겠지만 이 문제는 메모리의 최댓값이 너무 커 메모리 초과가 걸릴게 뻔했다.

배낭 문제의 변형본을 풀 때는 이 값이 배낭 문제의 '배낭의 크기'인지, '훔친 금액'인지 잘 판단해야겠다.