백준 7579번 - 앱

문제

백준 7579번 - 앱

아이디어

• 우선 그냥 눈으로 풀어봤다.

• 위 표는 0~c의 합의 비용으로 확보할 수 있는 최대 메모리를 구한 것이다. 6의 용량으로 최소 60의 메모리를 확보할 수 있으므로 6이 정답이다.
• 구한 과정을 코드로 구현해야 한다. 비용 6으로 최대 확보 메모리를 구할 때 다음과 같이 생각했다. 비용 c에서 합이 6 이하가 되는 조합 중 메모리의 합이 최대가 되는 것을 골랐다.
• 3+0+3, 0+4, 0+5 등이 있다. 그렇다면 각 비용에서 이렇게 모든 조합을 계산해야 하는 것일까?
• DP를 사용하여 해결할 수 있다. DP로 해결하면 현재 앱의 비활성화 비용(c)을 제외한 나머지 조합의 최댓값이 구해질 것이고, 그 최댓값과 현재 앱의 비활성화 비용을 포함한 결과 중 최댓값을 선택하여 해결할 수 있다.
• DP[i][j]를 i번째 앱까지 j의 비용으로 확보할 수 있는 최대 메모리로 가정한다.
• 현재 앱을 비활성화 하는 경우와 하지 않는 경우로 두 가지 경우가 있을 것이다.
• 현재 앱을 비활성화 한다면 비활성화 비용을 포함해야 하므로 이전번째 앱의 현재 앱 비활성화 비용을 제외한 비용에서 현재 앱을 비활성화했을 때 얻는 메모리를 더해준다.
• 그리고 현재 앱을 비활성화하지 않는 경우와 비교하여 더 큰 값으로 업데이트 해준다.

예상 시간 복잡도

• 앱의 수 : N
• 비활성화 비용의 합 : C (최대 10000)
• 예상 시간 복잡도 :O(N x C)

코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ_7579 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] appMemory = new int[n + 1];
        int[] c = new int[n + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            appMemory[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            c[i] = Integer.parseInt(st.nextToken());
            sum += c[i];
        }

        int[][] dp = new int[n + 1][sum + 1];

        for (int i = 1; i <= n; i++) { //i번째 앱
            for (int j = 0; j <= sum; j++) { //0 ~ 비활성화 비용(c)의 합
                if (j >= c[i]) { //현재 앱이 비활성화 가능하다면
                    //현재 앱을 비활성화 했을 때의 값
                    dp[i][j] = dp[i - 1][j - c[i]] + appMemory[i];
                }
                //현재 앱을 비활성화 했을 때와 하지 않았을 때를 비교
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
            }
        }

        //최소 m만큼 메모리를 확보할 수 있는 최소 비활성화 비용 출력
        for (int i = 0; i <= sum; i++) {
            if (dp[n][i] >= m) {
                System.out.println(i);
                return;
            }
        }
    }
}