BOJ) 앱 (7579 번)

앱

7579번: 앱

스마트폰 앱을 이용하는데, 사용자에게 더욱 빠른 반응을 위해 백그라운드에서 앱이 돌아간다.

하지만, 메모리는 한계가 존재하기 때문에 새로운 앱을 실행시키기 위해서 백그라운드에서 돌아가는 앱 중 일부를 종료시켜야 한다.

종료된 앱을 다음에 이용할 때 드는 비용을 최소화하는 문제다.

 

설명이 조금 복잡해서 여러번 틀렸지만, 문제를 제대로 이해한 뒤의 풀이 자체는 어렵지 않았다.

우선, 실행중인 앱의 정보를 저장해주었다.

현재 메모리를 얼마나 차지하는지, 종료한 뒤에 나중에 이용할 경우 드는 비용이 얼마인지를 저장했다.

 

dp를 이용해서 풀었는데, dp는 메모리가 아닌 이 비용으로 인덱스를 설정했다.

비용은 n  <= 100, c <= 100 이라 최대 10000 밖에 되지 않기 때문에 속도나 메모리 측면에서 효율적이라 판단했기 때문이다.

이 dp의 값에는 메모리 용량을 저장한다.

얼마의 비용에 어느 정도의 메모리를 확보할 수 있는지 저장하는 것이다.

 

현재 실행중인 앱을 순회하면서, (최대 비용인 10000 - 현재 앱의 비용) 부터  0의 dp를 탐색했다.

순회하는 비용에서 확보한 메모리가 0이 아닌 경우, 해당 비용의 메모리 + 현재 앱을 종료했을 때 비용을 최댓값으로 최신화 해주었다.

또한, 중요한 점은 현재 앱을 종료했을 시점의 확보된 메모리 양이다.

그래서 위의 dp 순회 이후, 현재 앱을 종료했을 때 비용과 최댓값을 최신화해주어 답을 구했다.

 

처음에는 메모리로 dp를 설정했었는데, 이렇게 되면 메모리가 넘어가는 경우 index 처리나 시간 효율성이 비효율적이기 때문에, 비용을 저장하는 것으로 바꿔주었다.

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class App_7579 {
  static final int MAX = 10000;

  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()), m = Integer.parseInt(st.nextToken());
    // n => 앱 개수 1 ~ 100, m => 메모리 1 ~ 10000000
    App[] app = new App[n];
    st = new StringTokenizer(br.readLine());

    for(int i=0; i<n; i++) {
      app[i] = new App(Integer.parseInt(st.nextToken()));
    }

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

    br.close();
    solution(n,m,app);
  }

  private static void solution(int n, int m,  App[] app) {
    int[] dp = initDP(n,app);

    int answer =0;
    for(int i=0; i<=MAX; i++) {
      if(dp[i] >= m) {
        answer = i;
        break;
      }
    }
    System.out.println(answer);
  }

  private static int[] initDP(int n, App[] app) {
    final int DEFAULT = 0;
    int[] dp = new int[MAX+1]; // m을 저장 m * cost 최대 => 10000, 인덱스는 cost
    dp[app[0].cost] = app[0].runningMemory;

    for(int i=1; i<n; i++) { // 100
      App now = app[i];
      for(int j=MAX-now.cost; j>=DEFAULT; j--) {
        if(dp[j] != DEFAULT) {
          dp[j + now.cost] = Math.max(dp[j + now.cost], dp[j] + now.runningMemory);
        }
      }
      dp[now.cost] = Math.max(dp[now.cost], now.runningMemory);
    }
    return dp;
  }

  private static class App {
    int runningMemory, cost;

    public App(int runningMemory) {
      this.runningMemory = runningMemory;
    }
  }
}