백준 7579 앱

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

분류: DP

---

접근방식

어떤 걸 기준으로 DP를 만들건지 어려웠던 문제였습니다...

결국 다른 블로그의 풀이를 참고하여 해결했습니다.

비용으로 확보할 수 있는 최대 메모리를 만들어가는 방식으로 해결했습니다.

점화식은 아래와 같습니다.

DP[cost] = max( DP[cost] , DP[cost - inActiveCost[app] + activeMemory[app] ) 

여기서 DP[cost]는 cost를 사용하여 확보할 수 있는 최대 메모리인데요,
DP[ cost - inActiveCost[app] ] 은 app을 아직 제거하기 전의 비용으로 확보할 수 있는 최대 메모리로
여기에 지금 앱을 제거해서 얻을 수 있는 비용을 더해주면 이게 현재 앱을 제거시켜서 확보할 수 있는 메모리가 되는거죠 :)

이걸 cost 0부터 전체 비용(모든 앱을 제거했을 때) - 현재 앱 제거비용 까지 DP를 업데이트 시켜주면 됩니다.
단, 0부터 시작하면 다음 계산에서 이번에 업데이트 한 결과가 반영되기 때문에 역순으로 갱신해줬습니다.

 

참고

https://life-with-coding.tistory.com/316

해결방법

let nm = readLine()!.split(separator: " ").map { Int(String($0))! }
let (n, m) = (nm[0], nm[1])
let activeMemory = readLine()!.split(separator: " ").map { Int(String($0))! }
let inActiveCost = readLine()!.split(separator: " ").map { Int(String($0))! }
let maxCost = inActiveCost.reduce(0, +)
var dp = [Int](repeating: 0, count: maxCost+1)

for app in 0..<n {
    for cost in (inActiveCost[app]...maxCost).reversed() {
        dp[cost] = max(dp[cost], dp[cost-inActiveCost[app]] + activeMemory[app])
    }
}

for cost in 0...maxCost {
    if dp[cost] >= m {
        print(cost)
        break
    }
}

 

배운점

하 이번도 쉽지 않았다....