P.7579 앱

코드

,

import java.io.*;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = line[0], m = line[1];
        int[] activate = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] deactivate = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int maxFee = Arrays.stream(deactivate).sum();
        int[][] dp = new int[n + 1][maxFee + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= maxFee; j++) {
                if (j < deactivate[i - 1]) dp[i][j] = dp[i - 1][j];
                else dp[i][j] = Math.max(dp[i - 1][j - deactivate[i - 1]] + activate[i - 1], dp[i - 1][j]);
            }
        }

        int i;
        for (i = 0; i <= maxFee; i++) {
            if (dp[n][i] >= m) break;
        }

        bw.write(Integer.toString(i));
        bw.flush();
    }
}

코드 설명

n개의 각 물건이 다른 가치 v와 다른 무게 w를 가지고 있고 한정된 무게 안에서 가장 높은 가치를 가질 수 있는 물건들을 골라내는 배낭 문제다.

2023.07.12 - [코딩테스트/백준] - P.12865 평범한 배낭

P.12865 평범한 배낭

 

이 문제에서 유의해야 할 점은 메모리 제한이 128MB인 것과 최대로 만들어낼 수 있는 메모리가 100,000,000인 것이다.

 

다음 dp 점화식은 우리가 배낭 문제를 접했을 때 가장 기본적으로 생각할 수 있는 점화식일 것이다.

dp[n][m] = m바이트 메모리를 확보할 때 n번째 앱을 비활성화할 경우 드는 최소 비용

n은 최대 100, m은 최대 10,000,000이므로 배열의 크기는 1,000,000,000이 되고 10^9이므로 dp배열은 1000MB라는 메모리를 필요로 한다.

 

그렇다면 점화식을 변경해야 한다.

dp[n][m] = 비활성화하는 비용이 m일 때 n번째 앱을 비활성화하여 확보할 수 있는 최대 메모리

위 배낭문제에서 점화식을 바꿀 수 있는 것은 v나 w밖에 없다.

n은 최대 100, m은 sum(재활성화 비용 리스트)이다.

(여기서 m은 문제의 m이 아닌 점화식의 m을 의미)

 

문제에서 제공되는 재활성화 비용은 최대 100이므로 m은 최대 100 * 100 = 10,000이며 배열의 크기는 1,000,000이므로 1MB라는 메모리를 필요로 하게 된다.

 

다음은 예시와 dp배열의 결과이다.

5 60
30 10 20 35 40
3 0 3 5 4

1번째 앱을 비활성화할 때 드는 비용은 3이다.

즉 0 ~ 2의 비용으로는 1번째 앱을 비활성화할 수 없고, 3부터 15의 비용을 지불할 때 1번째 앱을 비활성화할 수 있다.

 

2번째 앱을 비활성화할 때 드는 비용은 0이다.

0 ~ 15의 비용으로 2번째 앱을 비활성화할 수 있는데, 4의 비용을 지불할 때는 1번째 앱의 비용인 3을 지불하면서 2번째 앱을 비활성화할 수 있다.

즉, 4~15의 비용으로는 이전 앱과 함께 2번째 앱을 비활성화할 수 있다.

 

3번째 앱까지 보도록 하자.

3번째 앱을 비활성화할 때 드는 비용은 3이다.

마찬가지로 이 앱 단독으로는 3 ~ 15의 비용을 지불할 때만 비활성화할 수 있다.

그렇기 때문에 0 ~ 2의 비용으로는 이전 앱을 0 ~ 2의 비용으로 비활성화했을 때 얻는 메모리의 값을 얻을 수 있다.

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

3의 비용으로는 본인 자체를 비활성화할 수 있을 뿐더러 이전 앱을 0의 비용으로 비활성화할 수 있다.

4의 비용으로는 본인 자체를 비활성화할 수 있을 뿐더러 이전 앱을 1의 비용으로 비활성화할 수 있다.

.

.

.

m의 비용으로는 본인 자체를 비활성화할 수 있을 뿐더러 이전 앱을 'm - (본인을 비활성화하는 비용)'으로 비활성화할 수 있다.

dp[i][j] = Math.max(dp[i - 1][j - deactivate[i - 1]] + activate[i - 1], dp[i - 1][j]);

---

n번째 앱까지 순회를 마치면 n개의 앱을 활성화 / 비활성화했을 때 모든 비활성화 비용 조합에 대해 획득할 수 있는 최대의 메모리를 구하게 된다.

문제의 조건은 최소 비용으로 m바이트 이상의 메모리를 확보하는 것이다.

0부터 모든 비용의 합까지 순회를 해 보며 m바이트 이상의 메모리를 확보한 순간 반복문을 종료한다.

int i;
for (i = 0; i <= maxFee; i++) {
    if (dp[n][i] >= m) break;
}

// answer == i