문제
우리는 스마트폰을 사용하면서 여러 가지 앱(App)을 실행하게 된다. 대개의 경우 화면에 보이는 ‘실행 중’인 앱은 하나뿐이지만 보이지 않는 상태로 많은 앱이 '활성화'되어 있다. 앱들이 활성화 되어 있다는 것은 화면에 보이지 않더라도 메인 메모리에 직전의 상태가 기록되어 있는 것을 말한다. 현재 실행 중이 아니더라도 이렇게 메모리에 남겨두는 이유는 사용자가 이전에 실행하던 앱을 다시 불러올 때에 직전의 상태를 메인 메모리로부터 읽어 들여 실행 준비를 빠르게 마치기 위해서이다.
하지만 스마트폰의 메모리는 제한적이기 때문에 한번이라도 실행했던 모든 앱을 활성화된 채로 메인 메모리에 남겨두다 보면 메모리 부족 상태가 오기 쉽다. 새로운 앱을 실행시키기 위해 필요한 메모리가 부족해지면 스마트폰의 운영체제는 활성화 되어 있는 앱들 중 몇 개를 선택하여 메모리로부터 삭제하는 수밖에 없다. 이러한 과정을 앱의 ‘비활성화’라고 한다.
메모리 부족 상황에서 활성화 되어 있는 앱들을 무작위로 필요한 메모리만큼 비활성화 하는 것은 좋은 방법이 아니다. 비활성화된 앱들을 재실행할 경우 그만큼 시간이 더 필요하기 때문이다. 여러분은 이러한 앱의 비활성화 문제를 스마트하게 해결하기 위한 프로그램을 작성해야 한다
현재 N개의 앱, A1, ..., AN이 활성화 되어 있다 고 가정하자. 이들 앱 Ai는 각각 mi 바이트만큼의 메모리를 사용 하고 있다. 또한, 앱 Ai를 비활성화한 후에 다시 실행하고자 할 경우, 추가적으로 들어가는 비용(시간 등)을 수치화 한 것을 ci 라고 하자. 이러한 상황에서 사용자가 새로운 앱 B를 실행하고자 하여, 추가로 M 바이트의 메모리가 필요하다고 하자. 즉, 현재 활성화 되어 있는 앱 A1, ..., AN 중에서 몇 개를 비활성화 하여 M 바이트 이상의 메모리를 추가로 확보해야 하는 것이다. 여러분은 그 중에서 비활성화 했을 경우의 비용 ci의 합을 최소화하여 필요한 메모리 M 바이트를 확보하는 방법 을 찾아야 한다.
입력
입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활성화 되어 있는 앱 A1, ..., AN이 사용 중인 메모리의 바이트 수인 m1, ..., mN을 의미하며, 셋째 줄의 정수는 각 앱을 비활성화 했을 경우의 비용 c1, ..., cN을 의미한다
단, 1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000,000이며, 1 ≤ m1, ..., mN ≤ 10,000,000을 만족한다. 또한, 0 ≤ c1, ..., cN ≤ 100이고, M ≤ m1 + m2 + ... + mN이다.
출력
필요한 메모리 M 바이트를 확보하기 위한 앱 비활성화의 최소의 비용을 계산하여 한 줄에 출력해야 한다.
예제 입력
5 60
30 10 20 35 40
3 0 3 5 4예제 출력
6접근 방법
제한된 메모리에서 필요한 메모리를 확보하기 위해 앱을 비활성화할 때, 필요한 메모리를 확보하면서 비활성화 비용을 최소화 하는 방법을 찾아야 하는 문제입니다. 특정 용량 내에서 최대 가치를 찾는 문제인 배낭 문제와 비슷한 유형입니다. N의 최대값이 100이므로 각 앱을 비활성화할지 말지를 완전탐색으로 푼다면 시간 복잡도는 O(2^N) 이 됩니다. 따라서 완전탐색으로 풀 수 없는 문제입니다.
문제를 분석해보면, 최적 부분 구조 가 있다는 것을 알 수 있습니다. 최적 부분 구조란 큰 문제의 해답이 작은 문제들의 해답으로 이루어진다는 성질입니다. 예를 들어, 앱 1,3을 비활성화했을 때 필요한 최소 비용을 구한다고 합시다. 이제 앱 4를 추가해서 비활성화할 때 앱 1,3을 비활성화한 상태에서 비용과 메모리를 그대로 활용할 수 있습니다. 즉, 이전 계산 결과를 재활용할 수 있습니다.
같은 문제를 반복해서 계산할 필요가 없다는 점에서 DP 를 사용하여 문제를 풀 수 있고, DP 테이블은 배낭 문제에서 dp[무게]를 정의하는 것처럼 dp[비용]으로 정의할 수 있겠다는 생각이 들었습니다.
DP 테이블 정의
dp[c]를 비용 c를 사용하여 확보할 수 있는 최대 메모리라고 정의합니다.
초기화
비용이 0일 때 확보할 수 있는 메모리는 0입니다. dp 배열의 초기값을 0으로 만들어줍니다.
점화식
각 앱 i에 대해 비용이 c일 때, 현재 i번 앱을 비활성화하면 이전 상태에서 추가로 메모리를 확보할 수 있습니다.
dp[j] = Math.max(dp[j], dp[j - costs[i]] + bytes[i]);- 현재 앱을 비활성화 하지 않는 경우
이전 단계에서 얻은 비용dp[j]는 그대로 유지됩니다. - 현재 앱 i를 비활성화 하는 경우
비용 j 중에서 비활성화 비용 costs[i] 만큼 사용하게 됩니다. 즉, 비용 j에서 costs[i]를 뺀 비용으로 확보한 메모리에 현재 앱이 사용하고 있는 메모리 bytes[i]를 추가로 확보하게 됩니다.
같은 비용이라면 더 큰 메모리를 확보할 수 있는 경우를 선택합니다. 즉, 이 두 값 중 더 큰 값을 선택합니다.
시간 복잡도
N개의 앱에 대해 최대 sum(costs) 만큼의 비용에 대해 계산합니다. 각 앱에 대해 비용을 갱신하므로 시간 복잡도는 O(N * sumCosts) 가 됩니다. sumCosts는 각 앱의 비활성화 비용의 합입니다. N은 최대 100까지 가능하고 각 앱의 비활성화 비용은 최대 100이므로 최악의 경우 sumCosts는 10,000이 될 수 있습니다.
따라서, N * sumCosts = 100 * 10,000 = 1,000,000이 되어 제한 시간 1초 안에 해결할 수 있습니다.
전체 로직
- 각 앱의 메모리 사용량과 비활성화 비용을 입력 받습니다.
- dp 배열을 초기화하고 비용을 0에서 시작합니다.
- 각 앱에 대해 비용을 역순으로 처리하면서 현재 앱을 비활성화하는 경우와 그렇지 않은 경우를 고려해 DP 테이블을 갱신합니다.
- dp 배열에서 확보한 메모리가 M 이상인 최소 비용을 찾습니다.
- 최소 비용을 출력합니다.
역순 탐색 이유
한 번의 반복에서 갱신된 dp 값을 다시 참조하는 것을 방지하기 위함입니다. 예를 들어, 순차적으로 탐색할 경우 dp[j]를 갱신한 후, 그 값이 다음 dp[j+1]을 갱신하는 데 사용되면 같은 앱을 여러 번 비활성화 하는 것 과 같은 문제가 발생합니다. 역순 탐색을 하면 이전 상태에서만 계산이 이루어지기 때문에 같은 앱을 중복으로 비활성화하는 일이 생기지 않습니다.
예를 들어, 다음과 같은 입력이 주어진다고 가정합니다.
앱의 개수 N = 3
확보해야 하는 메모리 M = 6
각 앱이 사용하는 메모리 : 4MB, 2MB, 3MB
각 앱의 비활성화 비용 : 3, 1, 2
1번 앱(4MB, 비용 3) 처리 (순차 탐색):
dp[3] = max(dp[3], dp[0] + 4) → dp[3] = max(0, 0 + 4) = 4
dp[4] = max(dp[4], dp[1] + 4) → dp[4] = max(0, 0 + 4) = 4
dp[5] = max(dp[5], dp[2] + 4) → dp[5] = max(0, 0 + 4) = 4
dp[6] = max(dp[6], dp[3] + 4) → dp[6] = max(0, 4 + 4) = 8
dp[6]을 갱신할 때 이미 갱신된 dp[3]의 값을 참조하고 있습니다. 즉, 1번 앱을 비활성화해서 4MB를 확보한 상태에서 또다시 d[3]을 참조해 중복으로 앱 1을 비활성화한 것처럼 계산됩니다.
역순 탐색은 이미 갱신된 값을 다음 계산에 사용하지 않도록 보장합니다.
1번 앱(4MB, 비용 3) 처리 (역순 탐색):
dp[6] = max(dp[6], dp[6 - 3] + 4) → dp[6] = max(0, 0 + 4) = 4
dp[5] = max(dp[5], dp[5 - 3] + 4) → dp[5] = max(0, 0 + 4) = 4
dp[4] = max(dp[4], dp[4 - 3] + 4) → dp[4] = max(0, 0 + 4) = 4
dp[3] = max(dp[3], dp[3 - 3] + 4) → dp[3] = max(0, 0 + 4) = 4
예시
다음과 같은 입력이 주어진다고 가정합니다.
앱의 개수 N = 3
확보해야 하는 메모리 M = 6
각 앱이 사용하는 메모리 : 4MB, 2MB, 3MB
각 앱의 비활성화 비용 : 3, 1, 2
이때 모든 앱을 비활성화할 때 발생할 수 있는 총 비용을 계산합니다. 여기서는 sumCosts = 3 + 1 + 2 = 6 입니다.
각 앱을 비활성화할지 말지 결정하면서 DP 테이블을 갱신합니다.
이때, 각 앱을 순차적으로 처리하고 비용을 역순으로 처리하여 중복 계산을 방지합니다.
1번 앱 처리dp[3] 부터 dp[sumCosts] 까지 갱신합니다.j = 6일 때: dp[6] = max(dp[6], dp[6 - 3] + 4) = max(0, 0 + 4) = 4j = 5일 때: dp[5] = max(dp[5], dp[5 - 3] + 4) = max(0, 0 + 4) = 4j = 4일 때: dp[4] = max(dp[4], dp[4 - 3] + 4) = max(0, 0 + 4) = 4j = 3일 때: dp[3] = max(dp[3], dp[3 - 3] + 4) = max(0, 0 + 4) = 4
결과: dp = [0, 0, 0, 4, 4, 4, 4]
2번 앱 처리dp[6]부터 dp[1]까지 역순으로 갱신합니다.j = 6일 때: dp[6] = max(dp[6], dp[6 - 1] + 2) = max(4, 4 + 2) = 6j = 5일 때: dp[5] = max(dp[5], dp[5 - 1] + 2) = max(4, 4 + 2) = 6j = 4일 때: dp[4] = max(dp[4], dp[4 - 1] + 2) = max(4, 4 + 2) = 6j = 3일 때: dp[3] = max(dp[3], dp[3 - 1] + 2) = max(4, 0 + 2) = 4j = 2일 때: dp[2] = max(dp[2], dp[2 - 1] + 2) = max(0, 0 + 2) = 2j = 1일 때: dp[1] = max(dp[1], dp[1 - 1] + 2) = max(0, 0 + 2) = 2
결과: dp = [0, 2, 2, 4, 6, 6, 6]
3번 앱 처리dp[6]부터 dp[2]까지 역순으로 갱신합니다.j = 6일 때: dp[6] = max(dp[6], dp[6 - 2] + 3) = max(6, 6 + 3) = 9j = 5일 때: dp[5] = max(dp[5], dp[5 - 2] + 3) = max(6, 4 + 3) = 7j = 4일 때: dp[4] = max(dp[4], dp[4 - 2] + 3) = max(6, 2 + 3) = 6j = 3일 때: dp[3] = max(dp[3], dp[3 - 2] + 3) = max(4, 2 + 3) = 5
결과: dp = [0, 2, 2, 5, 6, 7, 9]
확보해야 하는 메모리 6 이상인 최소 비용은 dp[4]입니다. 이 예시의 출력은 4가 됩니다.
코드
import java.io.*;
public class BJ_G3_7579 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static int N; // 앱의 개수
static int M; // 필요한 메모리
static int[] bytes; // 앱이 사용하고 있는 메모리
static int[] costs; // 해당 앱을 비활성화 할 경우의 비용
static int sumCosts;
static int[] dp; // i만큼의 비용으로 확보할 수 있는 최대 메모리 크기
public static void main(String[] args) throws Exception {
init();
solve();
output();
}
public static void init() throws Exception {
String[] inputs = br.readLine().split(" ");
N = Integer.parseInt(inputs[0]);
M = Integer.parseInt(inputs[1]);
bytes = new int[N + 1];
costs = new int[N + 1];
String[] byteInputs = br.readLine().split(" ");
String[] costInputs = br.readLine().split(" ");
for (int i = 1; i <= N; i++) {
bytes[i] = Integer.parseInt(byteInputs[i - 1]);
costs[i] = Integer.parseInt(costInputs[i - 1]);
sumCosts += costs[i];
}
dp = new int[sumCosts + 1];
}
public static void solve() {
for (int i = 1; i <= N; i++) {
for (int j = sumCosts; j >= costs[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - costs[i]] + bytes[i]);
}
}
}
public static void output() {
for (int i = 0; i < dp.length; i++) {
if (dp[i] >= M) {
System.out.println(i);
break;
}
}
}
}'algorithm' 카테고리의 다른 글
| [BOJ] 10971. 외판원 순회2 (4) | 2024.09.03 |
|---|
