[백준 20667][java] 크롬

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

풀이

먼저 가장 단순하게 생각해보았을 때 크롬 탭 N개 중 1개, N개 중 2개 ... N개 중 N개를 골라서 목표 이상 cpu, memory를 확보하면서 중요도의 합이 가장 낮은 경우를 고르면 된다.

 

하지만 이 방법은 2^100이라는 경우의 수가 존재하기 때문에 시간 내에 해결할 수 없다.

 

다음은 DP를 생각할 수 있다.

 

가장 기초 냅색 문제인 배낭 문제처럼 dp[i][j][k]의 값을 i번째 크롬 탭까지 고려했을 때 확보한 CPU 사용량이 j이면서 확보한 메모리 할당량이 k일 때 중요도 합의 최솟값이라고 정의하면 된다.

 

그런데 이 방법 또한 시간 내에 해결할 수 없다.

 

N의 최대 값이 100, M의 최대 값이 1,000, K의 최대 값이 100,000이기 때문에 최대 100억이라는 공간이 필요하다.

 

일반적으로 1억 번 연산에 1초가 걸리는 점을 고려하면 제한 시간 내에 해결할 수 없다는 것을 알 수 있다.

 

 이 방법에서 dp 배열의 정의를 바꾸면 공간을 줄일 수 있다.

 

 dp[i][j][k]의 값을 i번째 크롬 탭까지 고려했을 때 확보한 CPU 사용량이 j이면서 중요도 합이 k일 때 메모리 할당량의 최대값

 

가장 큰 범위를 가진 메모리를 값으로 빼버리고 상대적으로 작은 범위를 가진 중요도를 배열의 인덱스로 넣는 것이다.

 

이렇게 dp 배열을 정의하면 문제를 해결할 수 있다.

 

이제 가장 기초적인 배낭 문제와 비교하면서 이 문제의 코드를 작성해보자.

 

아래는 가장 기초적인 배낭 문제이다.

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

 

가장 큰 다른 점은 다음과 같다.

배낭 문제는 배낭의 최대 무게가 K로 정해져있고 이 이상 넘어가는 경우는 고려할 필요가 없다.

크롬 문제는 CPU 사용량을 목표 사용량이 M으로 정해져있고 이 이상 넘어가는 경우도 고려해야 한다.

 

즉, 크롬 문제는 CPU 사용량이 M을 넘어가는 경우도 생각해야 한다.

 

단순하게 생각했을 때 100개 탭이 모두 CPU 사용량이 1,000일 수 있기 때문에 100,000개의 배열을 잡아야 한다.

 

하지만 말 그대로 최대 목표 사용량이 1,000이기 때문에 1,000개의 배열만 잡고 이 이상 넘어가는 경우는 1,000으로 처리하면 되기 때문에 1,000개의 배열만 잡으면 된다.

 

다음은 우리가 정의한 중요도의 합이다.

 

이는 CPU와 다르게 최대 중요도 합을 고려해야 한다.

 

중요도의 최대 값은 5이지만 총 100개의 탭이 존재할 수 있기 때문에 배열의 크기를 500으로 잡아야 한다.

 

이제 문제를 풀어보자.

 

dp를 정의하자.

        int[][][] dp = new int[n+1][m+1][501];

 

메모리 최대 값을 구하기로 결정했으니 모든 값을 최소 값으로 초기화하자.

 

그리고 아무것도 고를 수 없을 때 값을 0으로 저장하자.

 

        // 모든 값을 -INF로 초기화 한다.
        for (int i=0; i<=n; i++){
            for (int j=0; j<=m; j++){
                for (int p=0; p<=500; p++){
                    dp[i][j][p] = Integer.MIN_VALUE;
                }
            }
        }

        // 아무것도 없을 때
        dp[0][0][0] = 0;

 

dp를 시작하자.

        for (int i=1; i<=n; i++){
            int cpu = tabArr[i][0];
            int memory = tabArr[i][1];
            int importance = tabArr[i][2];
            for (int j=0; j<=m; j++){
                for (int p=0; p<=500; p++){
                    // tabArr[i]를 선택하지 않는 경우
                    dp[i][j][p] = Math.max(dp[i][j][p], dp[i-1][j][p]);
                    // tabArr[i]를 선택하는 경우
                    // 만약 cpu가 m이 넘을 경우 m으로 처리한다.
                    int nextCpu = Math.min(m, j+cpu);

                    // importance는 500을 넘을 수 없다.
                    int nextImportance = p+importance;
                    if (nextImportance > 500){
                        continue;
                    }

                    dp[i][nextCpu][nextImportance] = Math.max(
                            dp[i][nextCpu][nextImportance],
                            dp[i-1][j][p]+memory
                    );

                }
            }
        }

 

i번째 크롬 탭을 고르는 경우와 고르지 않는 경우를 생각해야 한다.

 

그리고 CPU 사용량이 M을 넘어가는 경우를 고려해야 하기 때문에 현재 시점에서 i번째 크롬 탭의 CPU 사용량과 중요도를 더해주는 방식을 사용했다.

 

이 방식을 사용하면 CPU 사용량이 M을 넘어갈 때 쉽게 M으로 만들어서 저장할 수 있다.

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.lang.Math;

public class Main{
    public static void main (String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken()); // 목표 cpu
        int k = Integer.parseInt(st.nextToken()); // 목표 메모리

        int[][] tabArr = new int[n+1][3];
        for (int i=1; i<=n; i++){
            st = new StringTokenizer(br.readLine());
            tabArr[i][0] = Integer.parseInt(st.nextToken());
            tabArr[i][1] = Integer.parseInt(st.nextToken());
            tabArr[i][2] = Integer.parseInt(st.nextToken());
        }

        // dp[i][j][k] : i번째 탭까지 고려했을 때 cpu가 j, 중요도가 k일 때 최대 메모리
        // cpu가 m이 넘을 경우 m으로 처리하기 위해 최대 m까지
        // 중요도는 최대 5이고 크롬 탭이 100개이기 때문에 최대 500
        int[][][] dp = new int[n+1][m+1][501];

        // 모든 값을 -INF로 초기화 한다.
        for (int i=0; i<=n; i++){
            for (int j=0; j<=m; j++){
                for (int p=0; p<=500; p++){
                    dp[i][j][p] = Integer.MIN_VALUE;
                }
            }
        }

        // 아무것도 없을 때
        dp[0][0][0] = 0;

        for (int i=1; i<=n; i++){
            int cpu = tabArr[i][0];
            int memory = tabArr[i][1];
            int importance = tabArr[i][2];
            for (int j=0; j<=m; j++){
                for (int p=0; p<=500; p++){
                    // tabArr[i]를 선택하지 않는 경우
                    dp[i][j][p] = Math.max(dp[i][j][p], dp[i-1][j][p]);
                    // tabArr[i]를 선택하는 경우
                    // 만약 cpu가 m이 넘을 경우 m으로 처리한다.
                    int nextCpu = Math.min(m, j+cpu);

                    // importance는 500을 넘을 수 없다.
                    int nextImportance = p+importance;
                    if (nextImportance > 500){
                        continue;
                    }

                    dp[i][nextCpu][nextImportance] = Math.max(
                            dp[i][nextCpu][nextImportance],
                            dp[i-1][j][p]+memory
                    );

                }
            }
        }

        int res = Integer.MAX_VALUE;
        for (int i=0; i<=500; i++){
            if (dp[n][m][i] >= k){
                res = i;
                break;
            }
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        if (res == Integer.MAX_VALUE){
            bw.write("-1");
        }
        else{
            bw.write(String.valueOf(res));
        }
        bw.close();


    }
}