[BOJ 20667, C++] 크롬

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

20667번: 크롬

 

 

풀이

CPU 사용량과 메모리 사용량, 중요도 세 가지를 고려해야 하는데, 두 개는 배열의 인덱스에 저장하고, 나머지 하나는 배열의 값에 저장하면 냅색문제로 풀 수 있게 됩니다.

배열의 인덱스에 넣을 값은 CPU의 최댓값이 1,000이고, 메모리는 100,000이고, 중요도는 500이므로 CPU의 사용량과 중요도를 인덱스에 넣으면 될 것 같습니다.

 

배열의 크기의 경우 dp[n][m][p]로 n번째까지 탭을 선택적으로 지웠을 때, 삭제한 cpu 사용량이 m이고, 중요도가 p인 것을 뜻합니다.

 

목표 CPU 사용량 삭제가 최대 1,000이니까 1,000을 넘어가면 목표한만큼 삭제를 했으니 1,000으로 고정시켜도 됩니다.

이제 for문을 통해 중요도가 1일 때 지울 수 있는 최대 메모리, 중요도가 2일 때 지울 수 있는 최대 메모리, ..., 중요도가 500일 때 지울 수 있는 최대 메모리를 구하여 목표 메모리 삭제량을 넘기면서 중요도가 제일 작은 것을 출력해주면 됩니다.

 

참고로 바텀업의 경우엔 배열을 훨씬 작게 만들어서 문제를 풀 수 있습니다.

 

 

코드

#include <iostream>
#include <cstring>
using namespace std;
using ll = long long;
 
const int N = 101, M = 1001, P = 501, MIN = -987654321;
int n, m, k, dp[N][M][P], cp[N], mem[N], pri[N];
 
int go(int x, int cpu_, int p) {
    if (x == n) return cpu_ == m ? 0 : MIN;
 
    int& ret = dp[x][cpu_][p];
    if (ret != -1) return ret;
 
    int ncpu = min(cpu_ + cp[x], m);
    ret = max(go(x + 1, cpu_, p), p - pri[x] >= 0 ? go(x + 1, ncpu, p - pri[x]) + mem[x] : MIN);
 
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    memset(dp, -1, sizeof(dp));
 
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        cin >> cp[i] >> mem[i] >> pri[i];
    }
 
    for (int i = 0; i < P; i++) {
        int x = go(0, 0, i);
        if (x >= k) {
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
 
    return 0;
}