[BaekJoon] 7579 앱 (Java)

1.  문제 링크

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

2.  문제

요약

• 앱들이 활성화 되어 있다는 것은 화면에 보이지 않더라도 메인 메모리에 직전의 상태가 기록되어 있는 것을 말합니다.
• 스마트폰의 메모리는 제한적이기 때문에 실행했던 모든 앱을 활성화된 채로 메인 메모리에 남겨둘 수 없어 메모리가 부족해지면 스마트폰의 운영체제는 활성화 되어 있는 앱들 중 몇 개를 선택하여 메모리로부터 삭제합니다. 이러한 과정을 '비활성화'라고 합니다.
• 비활성화된 앱들을 재실행할 경우 그만큼 시간이 더 필요하기 때문에 무작위로 앱들을 메모리에서 삭제하는 것은 효율적이지 않습니다.
• N개의 앱 $A_1, A_2, ..., A_N$이 활성화 되어 있다고 가정했을 때, 앱 $A_i$는 각각 $m_i$ 바이트만큼의 메모리를 사용하고 있습니다.
• 또한, 앱 $A_i$를 비활성화한 후에 다시 실행하고자 하는 경우, 추가적으로 $c_i$라는 비용이 들어갑니다.
• 이러한 상황에서 새로운 앱 B를 실행하고자 하여, 추가로 M 바이트의 메모리가 필요합니다.
• 현재 활성화 되어 있는 앱 $A_1, A_2, ..., A_N$ 중에서 몇 개를 비활성화 하여 M 바이트 이상의 메모리를 추가적으로 확보하려고 합니다.
• 그 중에서 비활성화 했을 경우의 비용 $c_i$의 합을 최소화하여 필요한 메모리 M 바이트를 확보하는 방법을 찾는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100보다 작거나 같은 N, 1보다 크거나 같고 10,000,000보다 작거나 같은 M이 주어지고 두 번째 줄에는 1보다 크거나 같고 10,000,000보다 작거나 같은 현재 활성화 되어 있는 앱 $A_1, A_2, ..., A_N$이 사용 중인 메모리의 바이트 수인 $m_1, m_2, ..., m_N$이 주어집니다. 세 번째 줄에는 0보다 크거나 같고 100보다 작거나 같은 각 앱을 비활성화 했을 때의 비용 $c_1, c_2, ..., c_N$이 주어집니다.
  • M ≤ $m_1 + m_2 + ... + m_N$
• 출력: 첫 번째 줄에 필요한 메모리 M 바이트를 확보하기 위한 앱 비활성화의 최소의 비용을 계산하여 출력합니다.

3.  소스코드

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

public class Main {
	static int N, M;
	static int[] memories, costs;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		M = scanner.nextInt();
		memories = new int[N];
		costs = new int[N];
		for(int idx = 0; idx < N; idx++) memories[idx] = scanner.nextInt();
		for(int idx = 0; idx < N; idx++) costs[idx] = scanner.nextInt();
	}
	
	static void solution() {
		int answer = Integer.MAX_VALUE;
		int[][] dp = new int[N][10001];
		for(int idx = 0; idx < N; idx++) {
			int cost = costs[idx], memory = memories[idx];
			for(int c = 0; c <= 10000; c++) {
				if(idx == 0) {
					if(c >= cost) dp[idx][c] = memory;
				} else {
					if(c >= cost) dp[idx][c] = Math.max(dp[idx - 1][c], dp[idx - 1][c - cost] + memory);
					else dp[idx][c] = dp[idx - 1][c];
				}
				if(dp[idx][c] >= M) answer = Math.min(answer, c);
			}
		}
		System.out.println(answer);
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

4.  접근

• 2차원 배열 dp[N][M]을 생성합니다.
  • dp[i][j] = i번째 앱까지 사용하여 비활성화 비용 j를 들였을 때의 확보된 메모리
• 첫 번째 앱에서는 해당 앱의 비활성화 비용 $c_1$ 이상에 대해서 $m_1$으로 값을 설정합니다.
• 두 번째 앱부터는 만약 현재 바라보는 비활성화 비용이 $c_i$보다 작다면 이전 앱에서 현재 바라보는 비활성화 비용에서의 메모리 수를 가져옵니다.
• 그렇지 않다면, 즉 현재 바라보는 비활성화 비용이 $c_i$보다 크거나 같다면, 해당 앱을 비활성화 시키지 않았을 때의 메모리인 dp[i - 1][j]와 해당 앱을 비활성화 시켰을 때의 메모리인 dp[i - 1][j - $c_i$] + $m_i$ 중 더 큰 값을 dp[i][j]의 값으로 설정합니다.
• 이렇게 dp[i][j]를 설정한 후, 각 dp[i][j]에 대해서 현재 확보된 메모리가 M보다 크거나 같은지 확인하고 만약 그렇다면 그 중 가장 작은 비용을 찾습니다.