✓

태그:

22. 동적 계획법 2 CLASS 5 ESSENTIAL

거꾸로 생각하기

풀이 비스무리한거 보기

주어진 앱을 종료할 때 비용이 들 때, 일정 이상의 메모리를 비우는 최소의 비용을 구하는 문제입니다. 배낭 문제와 상당히 유사하지만, 조건을 보면 조금 다릅니다. 배낭 문제의 무게에 해당하는 메모리의 범위가 10000000입니다. 메모리를 비울 때 필요한 최소 비용을 DP배열로 저장하면 메모리 초과가 나올 것입니다. 그래서 거꾸로 생각해야 합니다. 비용에 대해 비울 수 있는 최대의 메모리를 DP배열로 사용하는 것입니다. 이렇게 하면 0부터 비용을 올려가면서 비울 수 있는 메모리가 목표로 하는 메모리보다 크거나 같아지는 순간의 비용을 출력하면 됩니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-01-26 23:20:18

---