[Java+Python]7579번, 앱, 냅색문제

목차

 

문제

 

우리는 스마트폰을 사용하면서 여러 가지 앱(App)을 실행하게 된다. 

대개의 경우 화면에 보이는 ‘실행 중’인 앱은 하나뿐이지만 보이지 않는 상태로 많은 앱이 '활성화'되어 있다. 

앱들이 활성화되어 있다는 것은 화면에 보이지 않더라도 메인 메모리에 직전의 상태가 기록되어 있는 것을 말한다. 

현재 실행 중이 아니더라도 이렇게 메모리에 남겨두는 이유는 사용자가 이전에 

실행하던 앱을 다시 불러올 때에 직전의 상태를 메인 메모리로부터 읽어 들여 실행 준비를 빠르게 마치기 위해서이다.

하지만 스마트폰의 메모리는 제한적이기 때문에 한 번이라도 실행했던 모든 앱을 활성화된 채로 

메인 메모리에 남겨두다 보면 메모리 부족 상태가 오기 쉽다. 

새로운 앱을 실행시키기 위해 필요한 메모리가 부족해지면 스마트폰의 운영체제는 

활성화되어 있는 앱들 중 몇 개를 선택하여 메모리로부터 삭제하는 수밖에 없다. 

이러한 과정을 앱의 ‘비활성화’라고 한다.

메모리 부족 상황에서 활성화되어 있는 앱들을 무작위로 필요한 메모리만큼 비활성화하는 것은 좋은 방법이 아니다. 

비활성화된 앱들을 재실행할 경우 그만큼 시간이 더 필요하기 때문이다. 

여러분은 이러한 앱의 비활성화 문제를 스마트하게 해결하기 위한 프로그램을 작성해야 한다

현재 N개의 앱, $A_1,..., A_N$이 활성화되어 있다고 가정하자. 

이들 앱 $A_i$는 각각 $m_i$ 바이트만큼의 메모리를 사용하고 있다. 

또한, 앱 $A_i$를 비활성화한 후에 다시 실행하고자 할 경우, 추가적으로 들어가는 비용(시간 등)을 수치화한 것을 $c_i$라고 하자. 

이러한 상황에서 사용자가 새로운 앱 B를 실행하고자 하여, 추가로 M 바이트의 메모리가 필요하다고 하자. 

즉, 현재 활성화되어 있는 앱 $A_1,..., A_N$ 중에서 몇 개를 비활성화하여 M 바이트 이상의 메모리를 추가로 확보해야 하는 것이다. 

여러분은 그중에서 비활성화했을 경우의 비용 $c_i$의 합을 최소화하여 필요한 메모리 M 바이트를 확보하는 방법을 찾아야 한다.

 

입력

 

입력은 3줄로 이루어져 있다. 

첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 

둘째 줄의 N개의 정수는 현재 활성화되어 있는 앱 $A_1,..., A_N$이 사용 중인 메모리의 바이트 수인 $m_1,..., m_N$을 의미하며, 

셋째 줄의 정수는 각 앱을 비활성화했을 경우의 비용 $c_1,..., c_N$을 의미한다

단, $1 ≤ N ≤ 100$, $1 ≤ M ≤ 10,000,000$이며, $1 ≤ m_1,..., m_N ≤ 10,000,000$을 만족한다.

또한, $0 ≤ c_1, ..., c_N ≤ 100$이고, $M ≤ m_1 + m_2 + ... + m_N$이다.

 

출력

 

필요한 메모리 M 바이트를 확보하기 위한 앱 비활성화의 최소의 비용을 계산하여 한 줄에 출력해야 한다. 

 

풀이

 

이 문제는 동적계획법 1단계에서 풀었던 냅색 문제의 변형 버전이다.

 

변형이라 해봐야 뭐 대단한 건 아니고, 냅색문제는 가능한 최댓값을 찾는 문제였다면 여기선 최솟값을 찾아야 한다는 것 정도다.

 

문제의 조건대로 서술하자면,

 

'앱의 메모리 $m_i$와 재실행시 필요한 비용 $c_i$가 주어질 때, M를 확보하는데 드는 C의 최솟값을 구하라'

 

는 게 이 문제의 핵심일 것이다.

 

냅색문제로 환원시키자면 비활성화가 '물건을 넣는 행위'이고, 비용이 '무게', 메모리가 '가치'가 되기 때문에

 

비용(무게)의 합만큼의 배열을 만들고, 이를 통해 각 비용에서 얻을 수 있는 최대 메모리를 저장하면 된다.

 

이를 코드로 구현하면 대략 아래와 같은 흐름을 같는다.

 

1. 앱의 개수 n과 확보해야 하는 메모리 크기 n을 입력받은 후, 각 앱의 메모리와 비용을 memories, costs 배열에 저장한다.
2. 이어서 모든 앱의 비활성화 비용을 더한다. 이 값(sumCost)은 DP 테이블의 크기를 결정하게 된다.
3. 이어서 일차원 배열 dp(크기는 sumCost + 1)를 생성하고 모든 값을 Integer.MIN_VALUE로 초기화한다.
   각 인덱스에는 확보할 수 있는 최대 메모리가 저장되며, 비용이 0인 경우는 메모리를 확보하지 않기 때문에 0으로 초기화한다.
4. 이어서 모든 앱을 순회하며 각각의 비활성화 비용부터 sumCost까지 반복하면서 dp를 채워나간다.
   여기서 dp[j]는 비용이 'j'일 때 확보할 수 있는 최대 메모리를 나타낸다.
5. 마지막으로 dp 배열을 순회하며 m 이상의 메모리를 확보할 수 있는 최소 비용을 찾아 result에 저장하고 출력한다.

 

Java

 

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

public class Prob7579 {

	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());
		int m = Integer.parseInt(st.nextToken());

		int[] memories = new int[n + 1];
		int[] costs = new int[n + 1];

		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 1; i <= n; i++) {
			memories[i] = Integer.parseInt(st.nextToken());
		}

		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 1; i <= n; i++) {
			costs[i] = Integer.parseInt(st.nextToken());
		}

		int sumCost = 0;
		for (int cost : costs) {
			sumCost += cost;
		}

		int[] dp = new int[sumCost + 1];
		Arrays.fill(dp, Integer.MIN_VALUE);
		dp[0] = 0;

		for (int i = 1; i <= n; i++) {
			for (int j = sumCost; j >= costs[i]; j--) {
				dp[j] = Math.max(dp[j], dp[j - costs[i]] + memories[i]);
			}
		}

		int result = 0;
		for (int i = 0; i <= sumCost; i++) {
			if (dp[i] >= m) {
				result = i;
				break;
			}
		}

		System.out.println(result);
	}
}

 

Python

 

import sys

n, m = map(int, sys.stdin.readline().rstrip().split(" "))
memories = [0] + list(map(int, sys.stdin.readline().rstrip().split(" ")))
costs = [0] + list(map(int, sys.stdin.readline().rstrip().split(" ")))

sum_cost = sum(costs)
dp = [0] + [float("-inf") for _ in range(sum_cost)]

for i in range(1, n + 1):
    for j in range(sum_cost, costs[i] - 1, -1):
        dp[j] = max(dp[j], dp[j - costs[i]] + memories[i])

result = 0

for i in range(sum_cost + 1):
    if dp[i] >= m:
        result = i
        break

print(result)

 

Performance