[백준 20667][java] 크롬

https://www.acmicpc.net/problem/20667풀이먼저 가장 단순하게 생각해보았을 때 크롬 탭 N개 중 1개, N개 중 2개 ... N개 중 N개를 골라서 목표 이상 cpu, memory를 확보하면서 중요도의 합이 가장 낮은 경우를 고르면 된다. 하지만 이 방법은 2^100이라는 경우의 수가 존재하기 때문에 시간 내에 해결할 수 없다. 다음은 DP를 생각할 수 있다. 가장 기초 냅색 문제인 배낭 문제처럼 dp[i][j][k]의 값을 i번째 크롬 탭까지 고려했을 때 확보한 CPU 사용량이 j이면서 확보한 메모리 할당량이 k일 때 중요도 합의 최솟값이라고 정의하면 된다. 그런데 이 방법 또한 시간 내에 해결할 수 없다. N의 최대 값이 100, M의 최대 값이 1,000, K의 최대 값이..

2025.03.03