[백준 7579번] 파이썬(python) - 앱

http://www.acmicpc.net/problem/7579

7579번: 앱

 

# 조건

• 현재 N개의 앱, A1, ..., AN이 활성화 되어 있다고 가정하자.
• 이들 앱 Ai는 각각 mi 바이트만큼의 메모리를 사용하고 있다.
• 또한, 앱 Ai를 비활성화한 후에 다시 실행하고자 할 경우, 추가적으로 들어가는 비용(시간 등)을 수치화 한 것을 ci 라고 하자.
• 이러한 상황에서 사용자가 새로운 앱 B를 실행하고자 하여, 추가로 M 바이트의 메모리가 필요하다고 하자.
  • 즉, 현재 활성화 되어 있는 앱 A1, ..., AN 중에서 몇 개를 비활성화 하여 M 바이트 이상의 메모리를 추가로 확보해야 하는 것이다.
  • 여러분은 그 중에서 비활성화 했을 경우의 비용 ci의 합을 최소화하여 필요한 메모리 M 바이트를 확보하는 방법을 찾아야 한다.

 

입력

• 입력은 3줄로 이루어져 있다.
• 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다.
• 둘째 줄의 N개의 정수는 현재 활성화 되어 있는 앱 A1, ..., AN이 사용 중인 메모리의 바이트 수인 m1, ..., mN을 의미하며, 셋째 줄의 정수는 각 앱을 비활성화 했을 경우의 비용 c1, ..., cN을 의미한다
• 단, 1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000,000이며, 1 ≤ m1, ..., mN ≤ 10,000,000을 만족한다. 또한, 0 ≤ c1, ..., cN ≤ 100이고, M ≤ m1 + m2 + ... + mN이다.

 

# 접근 방법

• 배낭 채우기와 비슷한 문제이다 (Knapsack Problem)
• DP를 이용하여 풀어준다.
• dp i 행 j열은 i번째 앱까지 중 j코스트로 얻을 수 있는 최대 byte를 기록해준다.
  • dp 행의 개수 -> 앱의 개수
  • 열의 개수 -> cost 합의 수로 만들어준다.
• 행을 돌며 아래와 같은 과정을 수행
  • 현재 앱의 cost가 j보다 클 경우 끄지 못하므로 활성화
  • 그렇지 않다면 현재 앱을 끈 뒤의 byte와 그렇지 않을 경우의 byte 중 큰 값을 dp에 입력
• 현재 dp[i][j] 값이 M이상이라면 현재 cost, j와 이전의 result와 비교해 더 작은 값을 취해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
  
N, M = map(int, input().split())  
memory = [0] + [*map(int, input().split())]  
cost = [0] + [*map(int, input().split())]  
result = sum(cost)  
  
dp = [[0 for _ in range(sum(cost)+1)] for _ in range(N+1)]  
  
for i in range(1, N+1):  
    byte = memory[i]  
    pay = cost[i]  
  
    for j in range(1, sum(cost)+1):  
        # 현재 앱을 비활성화할만큼 cost가 충분하지 않는 경우우  
       if j < pay:  
           dp[i][j] = dp[i-1][j]  
  
       else:  
           # 같은 cost 내에서 현재 앱을 끈 뒤의 byte와 현재 앱을 끄지 않은 뒤의 byte를 비교  
           dp[i][j] = max(byte + dp[i-1][j-pay], dp[i-1][j])  
  
       if dp[i][j] >= M:  
           result = min(result, j)  
  
if M != 0:  
    print(result)  
else:  
    print(0)