[AlgorithmSolving][DP] JUNGOL_2616: 앱(App)
1. 문제 내용
-
문제:
우리는 스마트 폰을 사용하면서 여러 가지 앱(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 바이트를 확보하기 위한 앱 비활성화의 최소의 비용을 계산하여 한 줄에 출력해야 한다.
2. 문제 유형 파악
이 문제는 겉보기에는 필요한 메모리 M을 채우는 전형적인 배낭 문제(Knapsack Problem)처럼 보이지만, 일반적인 접근 방식과는 다른 발상의 전환이 필요한 심화 DP문제입니다.
-
배낭 문제의 변형: 각 앱은 메모리($m_i$, 무게 개념)와 비용($c_i$, 가치 개념)을 가지고 있으며, 우리는 비용의 합을 최소화하면서 특정 목표 메모리 이상을 확보해야 합니다.
-
치명적인 함정 (차원 설정의 문제)
-
만약 일반적인 배낭 문제철머 확보해야 할 메모리 M을 기준으로 DP 테이블을 만들려고 하면 문제가 발생합니다. 문제에서 M은 최대 10,000,000(천만)까지 주어지기 때문입니다.
-
10,000,000 크기의 배열을 선언하거나 2차원 테이블을 만들면 메모리 초과(Memory Limit Exceeded) 혹은 시간 초과가 발생합니다.
-
-
해결의 열쇠 (비용의 범위): 반면, 각 앱을 비활성화할 때 드는 비용 $c_i$는 0이상 100이하이며, 앱의 개수 N도 최대 100개입니다. 즉, 모든 앱을 다 비활성화해도 최대 총비용은 100x100 = 10,000을 넘지 않습니다.
-
따라서 이 문제는 메모리 크기가 아니라 비용을 DP 테이블의 인덱스로 삼아야 하는 역발상이 필요한 유형입니다.
3. 문제를 풀기 위한 핵심 아이디어
이 문제를 풀기 위한 핵심 로직은 “비용을 기준으로 얻을 수 있는 최대 메모리를 구한 뒤, 조건을 만족하는 최소 비용을 찾아내는 것”입니다.
-
DP 테이블의 정의 뒤집기
DP 배열을 다음과 같이 정의합니다.
- DP[j] = 비용의 합이 정확히 j일 때, 확보할 수 있는 “최대 메모리 크기”
- 이때, 인덱스 j는 최소 비용 0부터 최대 가능한 총 비용인 10,000까지의 범위를 가집니다.
-
배낭 문제 점화식 적용
모든 앱을 하나씩 확인하며, 각 앱을 “선택할 때(비활성화할 때)”와 “선태갛지 않을 때”를 고려하여 DP 테이블을 갱신합니다.
- 현재 앱의 비용이 c, 메모리가 m이라고 할 때, 비용 j를 만들 수 있다면 새로운 앱을 추가했을 때의 메모리는 DP[j-c]+m이 됩니다.
-
점화식:
\[DP[j] = \max(DP[j], DP[j - c] + m)\] - 이때, 동일한 앱이 중복으로 선택되는 것을 방지하기 위해 비용을 역순(최대 비용부터 c까지)으로 순회하며 1차원 배열을 갱신합니다.
-
최소 비용 탐색하기
반복문이 모두 끝나고 나면, DP 배열에는 각 비용(0부터 10,000까지)을 소모했을 때 얻을 수 있는 최대 메모리 값이 채워지게 됩니다.
- 이제 비용을 0부터 차례대로 살펴보면서, $DP[j] \ge M$ (필요한 메모리 이상을 확보함)을 만족하는 최초의 순간의 비용 j을 찾아 출력하면 그것이 바로 정답이 됩니다.
4. 코드
해당 문제의 코드는 다음과 같습니다.
import sys
def solve():
input = sys.stdin.readline
# 입력 값들을 받아온다
n, m = map(int, input().split())
memory_list = list(map(int, input().split()))
cost_list = list(map(int, input().split()))
sum_cost = sum(cost_list)
# 초기 1차원 dp배열 설정
dp = [0] * (sum_cost+1)
for i in range(n):
# 현재 비용과 메모리를 가져옴
cost = cost_list[i]
memory = memory_list[i]
# 2차원 배열을 사용할 경우 바로 이전인 i-1 배열만 사용하므로 두 개의 배열만 사용하기 때문에 dp와 next_dp 두 개의 dp 배열만 사용
next_dp = [0] * (sum_cost+1)
for j in range(sum_cost+1):
if j>=cost:
# j가 현재 cost보다 크거나 같을 때
# 이전 배열에서 j번째 위치의 메모리와 j-cost 번째 메모리에서 현재 메모리를 더한 값 중에 큰 값을 next_dp 배열에 저장
next_dp[j] = max(dp[j], dp[j-cost]+memory)
else:
# j가 cost보다 작다면 이전 dp배열에 있는 값을 넣어줌
next_dp[j] = dp[j]
# 미래의 dp배열을 현재의 dp배열로 교환
dp = next_dp
# 각 코스트별로 저장된 메모리 중에 m보다 크거나 같은 경우 해당 위치를 출력
for i in range(sum_cost+1):
if dp[i] >= m:
print(i)
break
solve()
Comments