[BOJ] 1579 : 앱

문제 링크

7579번: 앱 (acmicpc.net)

7579번: 앱

풀이

일단 내가 생각해낸 아이디어는 Cost 를 기준으로 오름차순 정렬한 다음 백트래킹으로 메모리를 더해가면서

메모리의 합이 M을 넘으면 그때의 Cost를 기존과 비교해서 최솟값을 저장하는 방식.

먼저 앱에 대해서 우리가 취할 수 있는 경우의 수는

1. 비활성화 한다

2. 그대로 둔다

두 가지 방법이 있다. 이를 바탕으로 백트래킹을 작성하면 아래의 코드가 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <climits>
#include <algorithm>
#include <tuple>
#include <cmath>
using namespace std;
typedef long long ll;
int N, M;
const int MAX_N = 10000000 + 5;
vector<int> Cost;
vector<int> Mem;
vector<pair<int, int>> App;
int ans = INT_MAX;
 
void backtracking(int depth, int mem_sum, int cost_sum) {
    if (mem_sum >= M) {
        ans = min(cost_sum, ans);
        return;
    }
    if (depth == N)
        return;
    int now_cost = App[depth].first;
    int now_mem = App[depth].second;
    backtracking(depth + 1, mem_sum + now_mem, cost_sum + now_cost);
    backtracking(depth + 1, mem_sum, cost_sum);
}
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    int mem, cost;
    App.push_back({ 0,0 });
    for (int i = 0; i < N; i++) {
        cin >> mem;
        Mem.push_back(mem);
    }
    for (int i = 0; i < N; i++) {
        cin >> cost;
        Cost.push_back(cost);
    }
    for (int i = 0; i < N; i++) {
        App.push_back({ Cost[i], Mem[i] });
    }
    sort(App.begin(), App.end());
    backtracking(0, 0, 0);
    cout << ans << "\n";
    return 0;
}
 
 

하지만 이렇게 쉬울리가 없다. 어림도없이 시간초과.

나는 냅색의 저장방식을 이용하려 했다 dp라는 2차원 배열을 만들어 dp[depth][cost] 에 비활성화 시킨 memory를 저장했다.

그렇게 해서 같은 depth에 같은 cost를 지불했다면 비활성화한 메모리가 적을 수록 비효율적인 것이다.

그래서 if(dp[depth][cost] >= 현재까지 memory 합) 이면 return; 을 했다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <climits>
#include <algorithm>
#include <tuple>
#include <cmath>
using namespace std;
typedef long long ll;
int N, M;
const int MAX_N = 10000000 + 5;
vector<int> Cost;
vector<int> Mem;
vector<pair<int, int>> App;
int ans = INT_MAX;
int dp[101][10005];
 
void backtracking(int depth, int mem_sum, int cost_sum) {
    if (mem_sum >= M) {
        ans = min(cost_sum, ans);
        return;
    }
    if (depth == N || dp[depth][cost_sum] >= mem_sum) {
        return;
    }
    int now_cost = App[depth].first;
    int now_mem = App[depth].second;
    dp[depth][cost_sum] = mem_sum;
    backtracking(depth + 1, mem_sum + now_mem, cost_sum + now_cost);
    backtracking(depth + 1, mem_sum, cost_sum);
}
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    int mem, cost;
    for (int i = 0; i < N; i++) {
        cin >> mem;
        Mem.push_back(mem);
    }
    for (int i = 0; i < N; i++) {
        cin >> cost;
        Cost.push_back(cost);
    }
    for (int i = 0; i < N; i++) {
        App.push_back({ Cost[i], Mem[i] });
    }
    sort(App.begin(), App.end());
    memset(dp, -1, sizeof(dp));
    backtracking(0, 0, 0);
    cout << ans << "\n";
    return 0;
}