편집 시간: 2022년 3월 31일 오후 9:53
코드
Algorithm/7579.py at main · Junroot/Algorithm
풀이
처음에는 아래와 같은 방식으로 dp로 풀려고 했다. 아래에서 f(i, m)의 정의는 0번째부터 i번째까지 앱으로 메모리 m을 비우기위한 최소 cost를 뜻한다.
$$ f(i, m) = min(f(i-1,m-m_i)+c_i,f(i-1,m)) $$
하지만, m의 범위가 10,000,000 까지기때문에 이 방법을 사용할 수 없다.
그래서 i와 cost를 사용해서 dp로 접근해봤다.
$$ f(i,c)=max(f(i-1,c-c_i)+m_i,f(i-1,c)) $$
c의 범위는 0에서 10000까지라서 최대 100 * 10000번 계산으로 계산할 수 있다. 그 다음, 이 관계식을 바텀업으로 구현하면 구현해둔 코드와 같아진다.