[백준 파이썬] 7579 앱

📌문제 출처

백준 단계별 문제풀이 - 동적 계획법 2
https://www.acmicpc.net/problem/7579

7579번: 앱

❓ 문제

❗ 풀이

• dp : 냅색 문제 응용

📗 풀이 코드

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
memories = list(map(int,input().split()))
costs = list(map(int,input().split()))
dp = [[0]*(sum(costs)+1) for _ in range(n)]
ans = sum(costs)
# dp[i][j] = i번째 App까지 확인했을 때 j 코스트 이상에서 얻을 수 있는 최고의 메모리
for i in range(n):
    byte, cost = memories[i], costs[i] # 확인할 app의 byte와 cost가져오기
    for j in range(sum(costs)+1):
        if cost > j : # 해당 app 비활성화 cost가 확인하는 cost보다 높다면
            dp[i][j] = dp[i-1][j] # 위의 행 결과(이전 app까지 확 인결과) 가져오기
        else : # 해당 app 비활성화가 가능한 cost라면
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-cost]+byte) # 이전 행 결과와 앞선 app 확인 결과 중 해당 app cost가 가능한 경우 중 최댓값
        if (dp[i][j] >= m) & (j < ans) : # dp[i][j]가 최소 메모리 기준을 만족하고 cost가 최소라면
            ans = j
print(ans) # 모든 dp를 채우고나서 답을 반환

📗 코드 해설

• 원하는 무게에서 가치의 최댓값을 구하는 냅색 문제의 응용 문제이다.
• 냅색 문제에서처럼 app을 하나씩 확인하며 cost를 0에서부터 최대인 sum(costs)까지 늘려가며
  cost가 j이고 app을 i번째까지 확인했을 때 메모리의 최대값을 d[i][j]에 넣어주자.
• dp를 모두 채웠을때 처음으로 m 이상인 메모리가 등장한 코스트를 정답으로 출력해주자
• 예제대로 dp를 채운다면 다음과 같다.
  
• 이 때 아래 그림처럼 중요한 순간들을 자세히 살펴보자.
  
• cost < 3인 경우에는 app을 비활성화할 수 없다.
  세번째 app을 확인하는 경우에, cost가 3이기에 j=2까지는 두번째 app의 결과를 그대로 가져온다.
• cost >= 3인 경우에는 app을 비활성화할 수 있다.
  해당 cost의 열에서 세번째 app의 cost를 지불하려면 두번째 app까지 확인한 결과에서 j-cost의 열의 결과값에(세번째 app의 cost 만큼 뺀) 세번째 app의 cost를 지불하면 된다.
  이 경우, dp[i][j] = dp[i-1][j-cost] + byte 가 성립한다.
• 그러나 세번째 app을 비활성화한 경우가 최대의 메모리가 아닐 수 있기에 두번째 app을 확인한 결과를 그대로 가져온 것과 대소 비교를 해주어야한다.
• 따라서 최종적으로 $dp[i][j] = max(dp[i-1][j], dp[i-1][j-cost]+byte)$가 성립하고,
  dp[3][3] = max(dp[2][3], dp[2][0]+byte) = max(40,10+20) = 40 으로 파란색 칸이 그대로 내려오게 된다.
• 위 경우를 전체 범위에서 반복을 해주고, ans값을 최소 cost(j 값)으로 갱신해준다.