boj 7579 : 앱

boj 7579 : 앱

https://www.acmicpc.net/problem/7579

 

아래와 같이 점화식을 정의한 DP 배열로 문제 해결 가능하다.

DP[i] : i의 비용만큼 들였을 때, 확보할 수 있는 최대 메모리
DP[i] = max(DP[i], DP[i - cj] + Memory[j])

 

물건의 개수는 최대 100개이고,  0 ≤ c1, ..., cN ≤ 100 이므로, DP 배열은 DP[100001]과 같이 잡으면 되며,

전체 (DP배열 크기) * (물건의 개수) 만큼 시간 소요된다.