BOJ 백준 20667번 크롬

 

BOJ 백준 20667 크롬

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

20667번: 크롬

N개의 탭 중 일부 탭을 지워서 CPU 사용량을 M 이상, 메모리 사용량을 K 이상 확보하면서 지운 탭의 중요도의 합을 최소로 하는 것을 목표로 한다. 이 때의 중요도 합의 최솟값을 구해야 한다.

 

 

 

우선 이 문제는 다이나믹 프로그래밍(Dynamic Programming)으로 해결해야 한다. 그러면 여기서 다이나믹 프로그래밍을 시행할 때 메모이제이션으로 사용할 배열인 dp 배열을 어떻게 설정할 것인지가 관건이다.

N개의 탭이 차례대로 첫 번째부터 N 번째까지 순서가 부여되었다고 했을 때, 문제에서 필요로 하는 데이터를 정의하면 다음과 같다.

 

 

 

prt[i]: i 번째 탭의 중요도

cpu[i]: i 번째 탭의 CPU 차지량

mem[i]: i 번째 탭의 메모리 차지량

dp[i][j][k]: 첫 번째부터 i 번째 탭까지 봤을 때 확보한 CPU 사용량이 j, 메모리 사용량이 k인 경우의 최소 중요도 합

 

 

그런데 이렇게 dp 배열을 선언하면 j와 k 각각의 최댓값을 고려했을 때 1,000 * 100,000 만큼의 메모리를 필요로 하므로 공간 복잡도뿐만이 아니라 시간 복잡도 면에서도 문제의 제한 조건에 위배된다. 따라서 dp 배열을 정의하는 관점을 새롭게 전환할 필요가 있어 보였다.

 

 

dp 배열에 CPU와 메모리 확보량에 따른 최소 중요도 합 자체를 저장하지 않고, 해당 중요도 합을 갖는 경우가 가능한지의 여부를 판단할 수 있는 배열을 선언하는 관점을 택했다. 메모리 사용량을 배열 원소의 개수로 반영하면 공간 복잡도를 초과하게 되므로, 중요도의 합과 CPU 확보량만을 배열의 원소 구분자로 사용하는 방법이 필요했다.

 

dp[i][j][k]: 첫 번째부터 i 번째 탭까지 봤을 때 지운 탭의 중요도 합이 j이면서 확보한 CPU 사용량이 k인 경우의 가능한 최대 메모리 확보량

 

 

dp[i][j][k] 배열 값을 구할 때, i 번째 탭을 지우지 않는 경우와 지우는 경우를 고려하여 식을 도출하면 다음과 같다.

 

dp[i][j][k] = max( dp[i -1][j][k], dp[i - 1][j - prt[i]][k - cpu[i]] + mem[i] )

 

 

그런데 어차피 loop를 돌며 첫 번째부터 N 번째 탭까지 차례대로 값을 업데이트해 나갈 것이므로 굳이 배열에 탭의 서수(i 번째)에 대한 정보를 저장할 필요 없이 슬라이딩 윈도(Sliding Window) 알고리즘을 이용하여 메모리를 절약할 수 있다.

 

 

 

dp[j][k]: 탭의 중요도 합이 j이면서 확보한 CPU 사용량이 k인 경우의 가능한 최대 메모리 확보량

dp[j][k] = max( dp[j][k], dp[j - prt[i]][k - cpu[i]] + mem[i] )

 

 

범위 내 모든 dp 배열 원소 값을 구한 후 dp[j][k] >= K와 k >= M을 만족하는 최소 j를 찾으면 된다.

그러나 이렇게 풀어서 제출해도 계속 AC를 받지 못해서 낙담하고 있던 중에, Sogang ICPC Team에서의 질문을 통해 djs100201님의 도움으로 문제를 해결했다. (큰 도움을 주신 djs100201님께 정말 감사드립니다.) 중요한 두 가지를 놓치고 있었는데, 이는 다음과 같다.

 

 

 

1) 알고리즘 시행 전 dp 배열을 0이 아닌 음의 무한값(예: -INF)으로 초기화해야 한다.

각 경우에 관해 도달 가능한 최대 메모리 확보량이 0인지, 아니면 실제로 도달이 불가능한 건지 구분이 되어야 하므로 알고리즘 시행 전 dp 배열을 -INF로 초기화한다.

 

2) CPU 확보량이 1,000을 넘어가는 경우가 발생할 수 있다.

예를 들어, 3개의 지울 수 있는 탭이 있고 목표 CPU 확보량이 1000, 목표 메모리 확보량이 3인데, 각 탭의 CPU 사용량과 메모리 할당량이 각각 1000, 1이면 3개의 탭을 모두 지울 경우의 CPU 확보량인 3000을 dp 배열에 반영할 수 없다. 그렇다고 가능한 모든 범위의 CPU 확보량을 dp 배열에 반영할 필요는 없다. 문제의 최대 CPU 확보량 상한인 1,000을 넘어가면 그 이후의 정확한 CPU 확보량이 얼마인지는 알 필요가 없으므로 이에 대한 경우를 한 가지 케이스로 예외 처리를 하면 된다.

 

k + cpu[i] > M_MAX + 1 ⇒ dp[j + prt[i]][M_MAX + 1] = max( dp[j + prt[i]][M_MAX + 1], dp[j][k] + mem[i] )

 

#include <cstdio>
#include <algorithm>
using namespace std;


const int INF = 0x3f3f3f3f;


const int N_MAX = 100;
const int M_MAX = 1000;
const int P_MAX = 500;


int N, M, K;
int dp[P_MAX + 1][M_MAX + 2];


int cpu[N_MAX + 1];
int mem[N_MAX + 1];
int prt[N_MAX + 1];


int main(){
    scanf("%d %d %d", &N, &M, &K);
    
    for (int i = 0; i <= P_MAX; i++){
        for (int j = 0; j <= M_MAX + 1; j++){
            dp[i][j] = -INF;
        }
    }
    
    for (int i = 1; i <= N; i++){
        scanf("%d %d %d", &cpu[i], &mem[i], &prt[i]);
    }
    
    dp[0][0] = 0;


    for (int i = 1; i <= N; i++){
        for (int j = P_MAX; j >= 0; j--){
            for (int k = M_MAX + 1; k >= 0; k--){
                if (j + prt[i] > P_MAX) continue;
                if (k + cpu[i] <= M_MAX){
                    dp[j + prt[i]][k + cpu[i]] = max(dp[j + prt[i]][k + cpu[i]], dp[j][k] + mem[i]);
                }
                if (k + cpu[i] > M_MAX){
                    dp[j + prt[i]][M_MAX + 1] = max(dp[j + prt[i]][M_MAX + 1], dp[j][k] + mem[i]);
                }
            }
        }
    }
    
    int ans = -1;
    for (int i = 0; i <= P_MAX; i++){
        for (int j = M; j <= M_MAX + 1; j++){
            if (dp[i][j] >= K){
                if (ans == -1 || ans > i){
                    ans = i;
                }
            }
        }
    }
    
    printf("%d\n", ans);


    return 0;
}