7579: 앱

문제 보기
배낭문제의 응용 버전이다.
문제에서 주어진 $M$을 딱 맞추지 않아도 $M$ 이상이 되는 모든 조합에 대해 생각하면 된다는 점을 이용하면,
비용에 대해 항상 누적 메모리의 최댓값만을 가져와도 된다는 것을 알 수 있다.

땨라서

$dp_i:i$만큼의 비용이 들었을 때 메모리 합의 최댓값

으로 정의해주면 된다.

저번 포스팅에서 다뤘던 배낭 문제에서의 최적화 아이디어를 이용하면
$S\to c_k$순으로 인덱스를 역순으로 움직이며 dp값을 찾을 수 있다.