[n7579] 앱 in python

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

7579번: 앱

---

(처음 든 생각)

최소비용,,, BFS인가,,, 

사실 잘 모르겠다..!

그래서 고민 끝에 풀이를 봤다.

(풀이 너무 찾아보는 거 아닌가 싶지만,

아무리 고민해도 모르겠어서 그냥 보고 배우는 게 낫겠다싶었다)

 

BFS가 아니라 DP 이용하는 것!

DP는 넘 어렵다아...

피보나치 수열 풀 땐 알겠는데,,,

이 문제에선 도저히 모르겠...

---

(DP 이용 풀이)

 

필요한 메모리 M 바이트를 확보하기 위한 앱 비활성화의 최소의 비용을 계산해야한다.

DP의 크기는 주어진 최소비용의 합+1

역순으로 배열 끝부터 작업 시작!

 

dp[ j ] = max( dp [ j ] ,  dp[ j + c [ i ] ) + a[ i ] )

 

하나를 예시로 들어보면,

i=0, j=15, M=30, C=3

dp[15]=max(dp[15], dp[15-3]+a[0])

dp[15], 즉 왼쪽항은 활성화 되어있는 값

dp[12]+a[0], 즉 오른쪽항은 a[0]을 비활성화한 값 (=확보한 메모리 값)

 

 

 

해당 위치의 dp값이 m이랑 같으면

해당 위치의 값을 출력해야한다. 

 

최소비용을 출력해야 하니까

dp==m가 처음 발견된 위치를 출력하고

for문 종료

 

뒤에서부터 계산하는 이유

: 앞에서부터 하게 되면 중복처리 되는 문제가 발생하기 때문

dp[A]에서 a[i]를 더했는데,

dp[B]에서 dp[A]+a[i]를 더하게 되면,

a[i]를 두번 더하게 되는거니까

 

 

* dp 문제 풀 때 *

-> 해당 위치의 값과 문제에서 요구하는 값을 비교하기,,,?

 

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
a = list(map(int, input().split()))
c = list(map(int, input().split()))
csum = sum(c)
dp = [0] * (csum + 1)

for i in range(n):
    for j in range(csum,c[i]-1,-1):
        dp[j] = max(dp[j], dp[j - c[i]] + a[i])

for i in range(csum+1):
    if dp[i] >= m:
        print(i, end='')
        break