[BOJ 7579, Python] 앱

문제 링크

BOJ 7579

분류

다이나믹 프로그래밍(dp), 배낭 문제(knapsack)

설명

해당 문제를 풀이할 때 중요하게 봐야 했던 부분을 개인적으로 꼽자면 문제 조건이었다고 생각한다.

사용 중인 메모리 바이트 조건은 10^7 이었고 활성화 어플의 수는 최대 100개, 비용의 경우도 100 이하의 조건을 만족해햐 했다.

가짓수를 확인할 용도로 메모리 바이트 조건을 활용하기엔 범위가 매우 넓었고 그에 따라 적절한 변수로 비용을 설정, 모든 비용마다 주소를 할당하여 최대한 줄일 수 있는 메모리를 기록하는 방식을 사용하겠다는 생각을 하게 되었다.

여기서 DP를 사용해야 한다는 것을 추측했고 더 나아가서 cost, value값이 각각 존재할 때 가치에 따라서 기존값을 갱신하는 방식을 사용했던 knapsack 알고리즘을 이용하여 해결하겠다는 설계를 해볼 수 있었다.

풀이 코드

# 앱

import sys

input = sys.stdin.readline

# 앱 갯수, 필요 메모리 입력
app_number, need_memory = map(int, input().split())

# 각 앱의 메모리와 비활성화 시의 비용 입력
app_memories = list(map(int, input().split()))
disable_costs = list(map(int, input().split()))

# 앱의 메모리와 비용 합쳐서 짝을 지어줌
memories_and_costs = list(zip(app_memories, disable_costs))

# 최대 필요 비용 연산
sum_cost = sum(disable_costs)

# 각 비용별 최대 절약 가능한 메모리 리스트 선언
cost_list = [0 for _ in range(sum_cost + 1)]

# Knapsack Algorithm

# 모든 앱에 대해 확인
for now_memory, now_cost in memories_and_costs:

    # 최대 필요 비용까지 조사
    for last_cost in range(sum_cost, -1, -1):

        # 최대 비용을 넘지 않는 선에서 확인
        if last_cost + now_cost <= sum_cost:

            # 기존 최대값보다 컸다면 갱신
            cost_list[last_cost + now_cost] = max(
                cost_list[last_cost + now_cost], cost_list[last_cost] + now_memory
            )

# 비용을 0에서부터 조사해서 기준 메모리 이상을 절약한 경우의 비용을 출력
for idx in range(sum_cost + 1):
    if cost_list[idx] >= need_memory:
        print(idx)
        break