백준 7579번 - 앱

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

7579번: 앱

# Approach)

제한 된 두가지의 자원(메모리, 비용)중 하나를 최소화하며 다른 하나를 최대화 해야한다.

고로 Knapsack 알고리즘을 떠올리자. dp배열을 어떻게 잡을지가 이 문제의 포인트이다.  

$dp[N][M]$ 으로  메모리를 채워가는경우 $O(n) = N \times M = 10^2 \times 10^7 = 10^9$으로 터질 가능성이 있다.

따라서 $ dp[N][sum(c)]$, $sum(c) = \displaystyle\sum_{i = 1}^{N} {c_{i}} \leq 10^2 \times 10^2 = 10^4$ 로 둔다면 $O(N \times sum(c)) = 10^2 \times 10^4 = 10^6$으로 넉넉하게 풀 수 있다.

 

# Definition)

$dp[i][j]$ : $A_{1}$부터 $A_{i}$까지의 앱에 대하여 최적으로 비활성화를 하여 비용이 $j$일때, 확보할 수 있는 최대한의 메모리

    

현재의 앱(비용을 c, 메모리를 m이라 두자)을 비활성화할 경우와 하지 않을 경우 2가지로 나눠서 생각해볼 수 있다.

$ dp[i][j]=$ $max(dp[i-1][j-c]+m,dp[i-1][j])$ 라는 점화식으로 문제를 풀 수 있게된다.

(이 점화식을 이용한 코드는 생략하겠다.)

Improvement

시간복잡도를 개선해보자. $1~i$까지의 구간을 귀납적으로 생각하여 위와 같은 점화식을 얻었다.

기준을 최적의 비활성화를 수행한 구간(즉, $1~i$)가 아닌 '각각의 앱에 대해 비활성화 여부 검사를 마쳤는지'로 생각보자.

DP문제(일반적으로 말해 점화식은) Induction, 하나의 최적해를 최적해의 합집합으로 쪼갤 수 있는 경우에 적용된다.

점화식 배열을 다음과 같이 다시 정의해보자.

 

$dp[i] :$ 이전의 수행은 몇번했는지 모르겠지만 임의의 수행후, 비용i를 써서 확보할 수 있는 최대한의 메모리 

 

아직 비활성화 여부 검사를 하지 않은 임의의 앱 $a$를 생각하자. 

 

1. 임의의 $dp[i]$에 대해 최적해가 $a$의 비활성화를 포함하는 경우

    현재까지 $a$는 비활성화 여부 검사를 하지 않았기에 $dp$의 모든 최적해는

    $a$의 비활성화를 포함하지 않았을 것이다.

    따라서 $dp[i]$의 최적해는 $a$의 비활성화 + $dp[i-a]$임을 알 수 있다.

    $dp[i] = dp[i-a] + cost(a)$로 갱신된다.

2. 임의의 $dp[i]$에 대해 최적해가 $a$의 비활성화를 포함하지 않는 경우

   이미 최적해이다.

 

하나의 최적해를 최적해의 합집합으로 쪼갤 수 있음을 보였다.

새로운 점화식은 $dp[i] = max(dp[i-app_{i}] + cost(app_{i})$, $dp[i]), app_{i} \in APP$ 라고 표현 할 수 있을 것이다.

순서와 관계없이 모든 $app_{i} \in APP$에 대해 한번씩 갱신해주면 된다.

 

시간복잡도는 크기 $sum(c)$인 배열을 앱의 개수, $N$만큼 iterate하기에 $O(sum(c) \times N)$로 이차원 배열을 이용한 경우와 같지만 일차원배열로 access의 시간이 단축된다는점, 메모리가 줄어든다는 메리트를 가진다.

---

dp배열의 초기화가 끝났다면 $dp[0] ~ dp[sum(c)]$를 순회하며 M이상이 나오는 가장 작은 인덱스를 출력하면 될 것이다.

 

#Code(c++)

#include <bits/stdc++.h>
using namespace std;
#ifdef ONLINE_JUDGE
  #define NDEBUG
#endif
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define command_param int argc, char *argv[]
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i < n; i++)
#define FOR(i, s, e) for(int i = s; i < e; i++)
#define pf first
#define ps second
#define pii pair<int,int> 
#define ll long long
#define lll __int128
#define endl "\n"
#define nulls '\0'
#define dkdk " "
const int INF = 987654321;
const ll INFLL = 1e13;
const int mod = 10007;
const int N = 1001;
const int st = 50;
int n, m, t, k;
vector<int> mv, cv;

void solve() {
  int sw = 0, sc = 0;
  for0(i, n) sw += mv[i];
  for0(i, n) sc += cv[i];
  int dp[sc+1]; memset(dp, 0, sizeof(dp));
  for0(i, n) {
    for(int j = sc; j >= cv[i]; j--) {
      dp[j] = max(dp[j], dp[j-cv[i]] + mv[i]);
    }
  }
  for0(i, sc+1) {
    if(dp[i] >= m) {
      cout << i; exit(0);
    }
  }
}

int main() {
  #ifdef NDEBUG 
    FASTIO;
  #else 
    freopen("input.txt", "r", stdin);
  #endif
  cin >> n >> m;
  mv.resize(n); cv.resize(n);
  for0(i, n) cin >> mv[i];
  for0(i, n) cin >> cv[i];
  solve();
}