[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

```@