이 문제는 활성화 되어 있는 앱들 중 몇 개를 고른 후 그 앱들의 메모리의 총합이 M 보다 같거나 커지게 했을 때 비용의 합이 최소가 되도록 하는 경우를 구하는 문제이며 정해는 동적계획법이다.얼핏 보면 메모리를 기준으로 동적계획법을 이용하여 해결해야겠다는 생각이 들지만 이는 O(N*(NM)) 이라는 시간복잡도를 갖게 되므로 제한시간 안에 해결되지 않는다.
조금만 생각을 해보면 이 문제를 활성화 되어 있는 앱들 중 몇 개를 골랐을 때 그들의 비용을 기준으로 동적계획법을 이용한다면 그 비용에 대한 가능한 최대의 메모리 합이 M 이상이 되는 최소 C 값을 구하는 문제로 바뀌게 되며, 이는 O(N * (NC)) 라는 시간복잡도를 갖게 되므로 제한시간 안에 무난하게 해결될 수 있다. (C 는 주어진 비용의 최댓값을 의미)
점화식의 정의는 다음과 같다.
- D[i,j] = i번째 앱까지 고려했을 때 고른 앱들의 비용의 합이 j 일 때 나올 수 있는 최대의 메모리 합
- D[i,j] = MAX( D[i-1 ,j] , D[i-1 , j-c[i]]+m[i] ])