[백준 - 7579] 앱

앱을 비활성화해 필요한 메모리 이상을 확보하면서 비용 합은 최소로 만들어야 한다. 구현에서는 확보한 메모리를 인덱스로 두고, 그 메모리를 만들기 위한 최소 비용을 저장했다.

dp[releasedMemory] = 최소 비활성화 비용

각 앱을 하나씩 보면서 메모리 인덱스를 큰 쪽부터 갱신해 같은 앱을 중복 선택하지 않게 했다. 같은 확보 메모리에 여러 선택이 도착하면 비용이 더 작은 값을 남겼다.

일반적인 배낭 문제와 달리 무엇을 최적화할지 먼저 뒤집어 본 풀이였다. 목표가 메모리이고, 최소화하는 값이 비용이므로 DP 축을 메모리로 두는 선택을 했다.

문제: 7579 앱 · 코드: GitHub에서 보기