7579 앱
-
백준 7579 앱Algorithm/BOJ 2021. 6. 2. 13:37
출처: https://www.acmicpc.net/problem/7579 분류: DP 접근방식 어떤 걸 기준으로 DP를 만들건지 어려웠던 문제였습니다... 결국 다른 블로그의 풀이를 참고하여 해결했습니다. 비용으로 확보할 수 있는 최대 메모리를 만들어가는 방식으로 해결했습니다. 점화식은 아래와 같습니다. DP[cost] = max( DP[cost] , DP[cost - inActiveCost[app] + activeMemory[app] ) 여기서 DP[cost]는 cost를 사용하여 확보할 수 있는 최대 메모리인데요, DP[ cost - inActiveCost[app] ] 은 app을 아직 제거하기 전의 비용으로 확보할 수 있는 최대 메모리로 여기에 지금 앱을 제거해서 얻을 수 있는 비용을 더해주면 이게..