07579번 앱

Problem link: https://www.acmicpc.net/problem/07579

Keywords: Dynamic programming, 0-1 Knapsack

부계로 문제 풀기를 진행하니 이쯤되면 내가 문제를 외우고 있는 것은 아닌가 의심이 된다. 내가 원하는 것은 면접이나 코딩테스트 때 풀이가 술술 나와주는 것인데, 이건 뭐…도움이 될까 싶다.

하여튼 각설하고, 이 문제는 관점을 조금만 비틀어 생각하면 0-1 knapsack 과 동일한 문제이다.

관점을 비틀라는 것이 뭔 개소리인가 하면,

• CACHE[i][c]: i번째 물건까지 사용해서 c 비용 이하로 확보할 수 있는 최대 메모리의 양 과 같이 캐시를 정의하고,
• DP를 돌린 후에, CACHE[N][c] >= M 이 되는 최소의 c를 찾으라는 말이다.

도둑이 보석을 쌔비는데, 배낭의 용량과 보석의 무게 (\(c_1\), \(c_2\), …) 가 있고, 보석의 가치 (\(m_1\), \(m_2\), …) 가 있다고 생각해보라. 이 문제는 배낭의 용량을 몇 쯤 챙겨가야 M원 이상 쌔벼나올 수 있는가를 묻는 문제이다. 비용을 보석의 무게로 생각해야하기 때문에 관점을 비틀라는 비교적 시적인 문구를 사용했다.

솔루션은 여기 에서 확인할 수 있다.