다이나믹 프로그래밍

백준 7579번 - 앱

https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net # Approach) 제한 된 두가지의 자원(메모리, 비용)중 하나를 최소화하며 다른 하나를 최대화 해야한다. 고로 Knapsack 알고리즘을 떠올리자. dp배열을 어떻게 잡을지가 이 문제의 포인트이다. $dp[N][M]$ 으로 메모리를 채워가는경우 $O(n) = N \times M = 10^2 \times 10^7 = 10^9$으로 터질 가능성이 있다. 따라서 $ dp[N][sum(c)]$, $sum(..