[백준/Java] 7579번 앱

백준 7579번 앱
https://www.acmicpc.net/problem/7579

올바른 점화식을 세우기까지 우여곡절이 있었던 문제.
같은 알고리즘을 도입하더라도 input을 올바르게 지정하지 못한다면 천차만별의 결과를 얻을 수 있다.

시도1 (메모리 초과)
dp[i][j] : 0번째부터 i번째 앱까지 고려하여 j이상의 메모리를 확보하는 최소비용

초기화
dp[0][j] = c[0] (if j <= m[0])
dp[0][j] = MAX (if j > m[0])
(MAX = 100*100 = 10000)

점화식
dp[i][j] = min{dp[i-1][j], dp[i-1]j-m[i]] + c[i]}

이 경우 dp[N-1][M]을 답으로 제출하게 되는데, 결국 메모리 초과에 걸렸다.
입력 조건에 주의해보자. array의 사이즈를 N*10000001로 잡아야 한다.

시도 2 (성공)
dp[i][j] : 0번째부터 i번째 앱까지 고려하여 j비용으로 확보할 수 있는 최대 메모리

초기화
dp[0][j] = m[0] (if j >= c[0])
dp[0][j] = 0 (if j < c[0])

점화식
dp[i][j] = max{dp[i-1][j], dp[i-1]j-c[i]] + m[i]}

시도 1과 언뜻 비슷해보여도 훨씬 우수한 메모리 성능을 가진다.
MAX 비용이 10000인 만큼, array의 사이즈를 N*10001으로 잡아도 충분히 풀 수 있다.