[BOJ] 앱 - 7579

🎨 문제

7579번: 앱

📘 풀이

배낭 문제와 유사한 문제입니다.

배낭 문제는 DP 배열을 다음과 같이 사용한다면

• 행: 넣을 수 있는 무게 
• 열: 물건의 종류
• 저장: 물건의 최대 가치

이 문제는 다음과 같이 생각할 수 있습니다.

• 행: 사용할 수 있는 비용
• 열: 앱의 종류
• 저장: 앱의 최대 메모리

DP의 시간 복잡도는 앱의 종류(N), 사용할 수 있는 최대 비용(MAX_COST)에 의해 N x MAX_COST가 됩니다.

N의 최대값은 100, 최대 비용은 단일 앱의 최대 비용(100) x 앱의 종류(100)이므로 최악의 경우 시간복잡도가 1,000,000 정도가 나옵니다.

DP 배열

우선 발생할 수 있는 최대 비용을 계산합니다.

// 발생할 수 있는 최대 비용
int maxCost = Arrays.stream(costs)
                .reduce(Integer::sum)
                .orElseThrow();		// costs 배열이 비어있는 경우 예외가 발생할 수 있다.

그리고 DP 배열을 선언합니다.

int[][] dp = new int[N + 1][maxCost + 1];   // 비용을 사용하여 얻을 수 있는 메모리

앞에서 설명했듯이 DP 배열의 한 칸의 행은 비용, 열은 종료시킬 앱을 의미한다.

배열 초기화

비용이 0인 경우와 아무 앱도 종료시키지 않은 경우는 0으로 초기화합니다. 자바는 int형 배열을 생성할 때 자동으로 0으로 초기화 되기 때문에 생략합니다.

그 후 배열을 하나씩 초기화 합니다.

int answer = maxCost;               // 최소 비용

for (int i = 1; i < N + 1; i++) {   // i번째 앱을 종료시키려 함

    int cost = costs[i - 1];		// i번째 앱의 비용
    int memory = memorySizes[i - 1];// i번째 앱의 메모리

    for (int j = 1; j < maxCost + 1; j++) { // j비용을 사용할 수 있음
    
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);    // 앱을 종료하지 않는 경우

        if (j - cost < 0) continue;     // 앱을 종료할 없다면 패스

        // 앱을 종료하지 않은 경우와 앱을 종료하는 경우 중 얻는 메모리가 큰 경우 사용
        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - cost] + memory);

        // 만약 요구 메모리를 충족했다면 j비용으로 비용 최솟값 초기화
        if (dp[i][j] >= M) {
            answer = Math.min(answer, j);
        }
    }
}

📒 예시

입력

5 60
30 10 20 35 40
3 0 3 5 4

출력

6

DP 배열

배열 전체

위 배열은 사용할 수 있는 비용에 따라 확보할 수 있는 메모리를 나타냅니다. 비용이 6인 부분부터 요구하는 메모리인 60을 충족하기 때문에 정답은 6이 됩니다.

📗 코드

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


public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);

        int[] memorySizes = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        int[] costs = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

		// 발생할 수 있는 최대 비용
        int maxCost = Arrays.stream(costs)
                .reduce(Integer::sum)
                .orElseThrow();
   		// 비용을 사용하여 얻을 수 있는 메모리
        int[][] dp = new int[N + 1][maxCost + 1];
        int answer = maxCost;	// 최소 비용

        for (int i = 1; i < N + 1; i++) {   // i번째 앱을 종료시키려 함

            int cost = costs[i - 1];		// i번째 앱의 비용
            int memory = memorySizes[i - 1];// i번째 앱의 메모리

            for (int j = 1; j < maxCost + 1; j++) { // j비용을 사용할 수 있음
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);    // 앱을 종료하지 않는 경우

                if (j - cost < 0) continue;     // 앱을 종료할 수 없다면 패스

                // 앱을 종료하지 않은 경우와 앱을 종료하는 경우 중 얻는 메모리가 큰 경우 사용
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - cost] + memory);

                // 만약 요구 메모리를 충족했다면 j비용으로 비용 최솟값 초기화
                if (dp[i][j] >= M) {
                    answer = Math.min(answer, j);
                }
            }
        }

        System.out.println(answer);
    }
}