[Code Tree] 폭탄 해체 작업

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-the-bomb-dismantling/description

폭탄 해체 작업 설명 | 코드트리

 

풀이

첫 번째 풀이 - 시간 오름차순 그리디

처음 이 문제를 보았을 때, 떠오른 방식은 시간 오름차순 그리디 방식이었습니다.

 

시간 제한이 작은 폭탄 순서대로 폭탄을 해체하는 방식입니다.

 

다음과 같이 N이 2이면서 (시간 제한, 점수) 쌍이 (1, 3), (2, 4), (3, 3)인 경우를 생각해봅시다.

이 경우 시간 오름차순 기준 그리디로 접근하면 문제를 해결할 수 있습니다.

 

첫 번째와 두 번째 폭탄을 순서대로 해체하면 2초 동안 최대 점수인 7점을 얻을 수 있습니다.

 

하지만 이 방식의 경우 반례가 존재합니다.

 

다음과 같이 N이 2이면서 (시간 제한, 점수) 쌍이 (1, 3), (3, 4), (3, 5)인 경우를 생각해봅시다.

만약 시간 오름차순 기준 그리디 방식으로 해결할 경우 무조건 첫 번째 폭탄을 선택하게 되고 그 다음 폭탄으로 두 번째 폭탄과 세 번째 폭탄 중 하나를 선택해야 합니다.

 

하지만 최대 점수를 얻으려면 첫 번째 폭탄을 선택하지 않고 두 번째 폭탄과 세 번째 폭탄을 선택해야 9점을 얻을 수 있습니다.

 

즉, 시가 오름차순 기준 그리디 방식으로 이 문제를 해결할 수 없습니다.

 

두 번째 풀이 - dp

그 다음으로 생각한 방식은 dp입니다.

 

첫 번째 방식의 한계를 극복하려면 폭탄을 선택하는 경우와 폭탄을 선택하지 않는 경우를 모두 고려해야 합니다.

 

2차원 dp를 정의하였고 dp[i][j]를 다음과 같이 정의했습니다.

 

dp[i][j] : i번째 폭탄까지 고려했을 때, j개 폭탄을 해제했을 때 점수 최대 값

 

dp를 사용하면 첫 번째 풀이의 한계를 극복할 수 있을 것이라고 생각했습니다.

// dp로 해결
// dp[i][j] : i번째 폭탄까지 고려했을 때, j개 폭탄을 해제했을 때 점수 최대 값
import java.util.Scanner;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Bomb[] bombs = new Bomb[n+1];
        bombs[0] = new Bomb(-1, -1);
        for (int i = 1; i <= n; i++) {
            bombs[i] = new Bomb(sc.nextInt(), sc.nextInt());
        }
        Arrays.sort(bombs);

        int[][] dp = new int[n+1][n+1];
        // dp 초기화 
        for (int i=0; i<=n; i++){
            for (int j=0; j<=n; j++){
                dp[i][j] = -1;
            }
        }

        // 0번째까지 선택한 것은 무조건 0
        for (int i=0; i<n; i++){
            dp[0][i] = 0;
        }
        for (int i=1; i<=n; i++){
            for (int j=1; j<=i; j++){

                // i번째를 선택하는 경우
                // dp[i-1][j-1]이 가능한 경우이면서 시간이 지나지 않은 상태여야 함
                if (dp[i-1][j-1] != -1 && bombs[i].time >= j){
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1] + bombs[i].score);
                }

                // i번째를 선택하지 않는 경우
                if (dp[i-1][j] != -1){
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j]);
                }
            }
        }
        int res = 0;
        for (int i=0; i<=n; i++){
            res = Math.max(res, dp[n][i]);
        }
        System.out.println(res);
    }
}
class Bomb implements Comparable<Bomb>{
    int score;
    int time;
    public Bomb(int score, int time){
        this.score = score;
        this.time = time;
    }
    @Override
    public int compareTo(Bomb bomb){
        if (this.time == bomb.time){
            return Integer.compare(bomb.score, this.score);
        }
        return Integer.compare(this.time, bomb.time);
    }
}

 

하지만 이 방식의 경우 공간 복잡도가 O(N^2)가 됩니다.

 

N의 최대 값은 10,000이기 때문에 최악의 경우 dp 2차원 배열을 만들기 위해 100,000,000의 공간이 필요합니다.

 

int형 배열을 만든다고 하면 int의 크기가 4byte이기 때문에 400,000,000 byte가 필요하고 이는 약 400MiB에 해당합니다.

 

문제의 메모리 제한이 176MiB이기 때문에 dp로 문제를 풀게 되면 메모리 초과가 발생합니다.

 

세 번째 풀이 - 시간 내림차순 그리디

첫 번째 방식은 반례가 존재하고 두 번째 방식은 메모리 초과가 발생합니다.

 

이를 해결하기 위해 첫 번째 풀이에서 그리디가 실패한 이유를 분석했습니다.

 

다음과 같이 여러 개의 폭탄이 있는 경우를 가정해보겠습니다.

시간 오름차순으로 진행하게 되면 너무 변수가 많습니다.

 

가장 먼저 해체할 폭탄을 골라야하는데 위 경우 모든 폭탄을 먼저 선택하는 경우를 고려해야 합니다.

 

즉, 경우의 수가 너무 많기 때문에 현재 시점에서 최선의 폭탄을 고른다고 최적의 해가 되지 않을 수 있습니다.

 

위 같은 경우만 보더라도 가장 먼저 해체할 폭탄을 고르기 위한 최선의 선택은 가장 아래의 점수가 5짜리 폭탄을 해체하는 것입니다.

 

하지만 해당 폭탄을 먼저 해체하는 순간 시간 제한이 1인 폭탄을 고를 수가 없습니다.

 

점수 5짜리 폭탄은 시간 제한이 길기 때문에 시간 제한이 짧은 폭탄들을 먼저 해체하고 가장 나중에 해체하는 것이 최적의 해가 됩니다.

 

이러한 문제를 해결하기 위해서는 단순히 시간 내림차순 기준으로 폭탄을 해체하면 됩니다.

 

다시 같은 상황을 생각해봅시다.

첫 번째로 해체할 폭탄의 경우의 수는 6개나 되지만 마지막으로 해체할 폭탄을 고르는 경우의 수는 1입니다.

 

즉, 마지막으로 해체할 폭탄부터 첫 번째로 해체할 폭탄을 고르는 방식을 선택하면 그리디 방식으로 문제를 해결할 수 있습니다.

 

priority Queue를 활용하면 그리디 방식으로 문제를 해결할 수 있습니다.

 

// dp로 해결
// dp[i][j] : i번째 폭탄까지 고려했을 때, j개 폭탄을 해제했을 때 점수 최대 값
import java.util.Scanner;
import java.util.Queue;
import java.util.PriorityQueue;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Bomb[] bombs = new Bomb[n];
        Queue<Integer> pq = new PriorityQueue();
        for (int i = 0; i < n; i++) {
            bombs[i] = new Bomb(sc.nextInt(), sc.nextInt());
        }
        Arrays.sort(bombs);
        int res = 0;
        int bombIdx = n-1;
        // 뒤에서부터 차례대로
        for (int time=10001; time>0; time--){
            // 지금 시간에 해체할 수 있는 모든 폭탄을 pq에 넣는다.
            while (bombIdx >=0 && bombs[bombIdx].time >= time){
                pq.add(-bombs[bombIdx--].score);
            }
            if (pq.isEmpty()){
                continue;
            }
            // 뽑는다.
            int score = pq.remove();
            res += -score;
        }
        System.out.println(res);
    }
}
class Bomb implements Comparable<Bomb>{
    int score;
    int time;
    public Bomb(int score, int time){
        this.score = score;
        this.time = time;
    }
    @Override
    public int compareTo(Bomb bomb){
        if (this.time == bomb.time){
            return Integer.compare(this.score, bomb.score);
        }
        return Integer.compare(this.time, bomb.time);
    }
}