알고리즘/백준

[백준] 7579. 앱 (python)

AquaplaneMode 2023. 1. 4. 21:18

문제 설명

각 앱은 사용중일 때의 메모리(m)과, 비활성화 했을 경우의 비용(c)에 대한 정보를 가지고 있다.
필요한 추가 메모리(M)가 주어졌을 때, 해당 메모리를 확보할 수 있는 최소 비활성화 비용을 구하는 문제이다.

문제 풀이

해당 문제는 동적 계획법(Dynamic Programming), 그 중에서도 냅색(Knapsack) 문제이다.

  1. 우선 dp 행렬을 하나 선언한다.
  • 가로 길이는 모든 앱을 비활성화 했을 때의 비용+1, 세로 길이는 앱의 개수+1 만큼 설정한다.
  • dp[i][j]는 i번째 까지의 앱을 활성화 하거나 비활성화하여 j 만큼의 비용이 들었을 때, 확보할 수 있는 최대한의 추가 메모리를 의미한다.
  1. 점화식에 따라 dp 배열을 갱신해준다.

if col_idx < app_deact:
    dp[row_idx][col_idx] = dp[row_idx-1][col_idx]

else:
    dp[row_idx][col_idx] =\
        max(dp[row_idx-1][col_idx], dp[row_idx-1][col_idx-app_deact] + app_act)

if(첫 번째 분기)문은 "예산이 비용보다 적은 경우"를 의미한다.
현재 사용할 수 있는 비용이 앱 비활성화할 시의 비용보다 작기 때문에, 앱을 비활성화 할 수 없고, 이전의 상태를 그대로 따른다.

else(두 번째 분기)문은 예산이 비용보다 큰 경우를 의미한다.
따라서 앱을 활성화할지, 비활성화할지 선택할 수 있다.

  • 현재 앱을 비활성화 하지 않고, 이전 상태를 그대로 가져가는 것
  • 이전 앱을 활성화하여 추가 예산을 확보하고, 현재 앱을 비활성화하는 것

두 가지 경우를 비교하여 더 많은 추가 메모리를 확보할 수 있는 경우를 선택하면 된다.

갱신이 끝난 dp 배열은 다음과 같은 모습일 것이다.

0 1 2 3 4 5 6
- 0 0 0 0 0 0 0
(30, 3) 0 0 0 30 30 30 30
(10, 0) 0 10 10 40 40 40 40
(20, 3) 0 10 10 40 40 40 40
(35, 5) 0 10 10 40 40 40 60
(40, 4) 0 10 10 40 40 50 60

본 문제에서는 목표로 하는 추가메모리만큼을 확보할 수 있는 최소 비용을 구하는 것이기 때문에, 갱신되는 값이 목표로 하는 추가 메모리보다 클 경우, 해당 column 값이 최소값이라면 계속 갱신해주는 식으로 답을 구할 수 있다.

코드

import sys
input = sys.stdin.readline

# 입력값 받기
num_apps, mem_req = map(int, input().split()) # 앱 개수, 필요 메모리
mem_act = list(map(int, input().split())) # 활성화 시의 메모리
mem_deact = list(map(int, input().split())) # 비활성화 시의 메모리

# 0-1 knapsack
deact_all = sum(mem_deact)
dp = [[0] * (deact_all+1) for _ in range(num_apps+1)]
answer = deact_all+1

for row_idx in range(1, num_apps+1):

    app_act = mem_act[row_idx-1]
    app_deact = mem_deact[row_idx-1]

    for col_idx in range(1, deact_all+1):

        if col_idx < app_deact:
            dp[row_idx][col_idx] = dp[row_idx-1][col_idx]
        else:
            dp[row_idx][col_idx] =\
                max(dp[row_idx-1][col_idx], dp[row_idx-1][col_idx-app_deact] + app_act)

        if dp[row_idx][col_idx] >= mem_req:
            answer = min(answer, col_idx)

if mem_req:
    print(answer)
else:
    print(0)

배운 점

냅색 문제는 예산이 주어졌을 때, 취할 수 있는 물건들의 가치의 합이 "최대"가 되는 경우를 찾는 문제이다.

본 문제를 냅색 문제와 비교하자면, 물건들의 가치의 합이 어느 정도 이상일 때의 "최소" 예산을 구하는 문제로 치환할 수 있다.

코드로 본다면 두 문제는 완전히 동일한 문제라고 볼 수 있지만, 정답은 배열의 원소 내에서 찾아야 한다는 고정관념에 빠져 문제를 제대로 풀지 못한 점이 아쉽다.

문제를 푸는 방법은 같고, 그 안에서 정답을 취하는 방법이 다를 수 있음을 고려하자.

저작자표시 비영리 (새창열림)