[백준 - 20666번] 인물이와 정수 - Java

문제링크

https://www.acmicpc.net/problem/20666

문제

티어: 골드 3
알고리즘: 그리디, 우선순위 큐

인물이와 정수는 친한 친구이다. 어느 날 인물이가 하는 게임에 관심이 생긴 정수는 게임에 대해 이것저것 물어보았다.

게임에는 N마리의 몬스터가 있고, M마리의 몬스터를 잡으면 이 게임을 클리어하게 된다. 몬스터는 한 번에 하나씩만 잡을 수 있다.

각각의 몬스터를 잡으면 그 몬스터가 주는 아이템을 얻을 수 있다. 즉 a번 몬스터를 잡으면 a번 아이템을 얻을 수 있고, a번 아이템을 다른 경로로 얻을 수 있는 방법은 없다.

게임을 많이 했던 인물이는 각 몬스터들을 한 번씩 잡아서 모든 아이템을 갖고 있다. 그래서 인물이는 각 몬스터의 난이도가 Ci라고 했지만, 정수는 게임을 처음 해서 아이템이 없기 때문에 그보다 더 어려워질 수 있다.

인물이는 정수에게 권장 아이템에 관한 팁 p개를 알려주었다. 팁은 a, b, t의 형태를 갖고 있고, a 아이템 없이 b 몬스터를 잡을 경우 t 만큼 어려워진다는 것을 말한다.

정수는 게임을 하면서 만나는 몬스터의 최대 난이도를 이 게임의 난이도라고 생각한다. 인물이는 정수가 게임을 너무 어렵게 느끼지 않도록 몬스터를 잡는 순서를 잘 정해주었다. 정수가 게임을 클리어할 때 느끼는 난이도를 최대한 줄여보자.

입력

첫 번째 줄에 두 정수 N, M 이 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ N)

두 번째 줄에 N 개의 정수 C1, C2, ... , CN 가 공백으로 구분되어 주어진다. Ci 는 인물이에게 i 번째 몬스터의 난이도를 말한다. (1 ≤ Ci ≤ 1,000,000,000)

세 번째 줄에 정수가 받은 팁의 개수 p 가 주어진다. (0 ≤ p ≤ 300,000)

다음 p 줄에 걸쳐 a, b, t 가 주어진다. a 아이템이 없어 b 몬스터를 잡을 때 t 만큼 난이도가 올라가게 된다. (1 ≤ a, b ≤ N, 1 ≤ t ≤ 1,000,000,000)

두 팁의 a, b가 같은 경우는 주어지지 않는다.

출력

정수가 게임을 클리어할 때 느끼는 난이도의 최소값을 출력한다.

풀이

목표는 정수가 게임을 클리어할 때 느끼는 난이도를 최소로 해줘야 한다.

난이도를 최소로 하기 위해서는 난이도가 낮은 몬스터부터 잡아야 한다.

팁이 없는 경우는 간단하지만, 팁이 있는 경우가 조금 까다롭다.

이 해결하기 위한 아이디어는 최초 접근이 중요하다.

정수는 처음에 어떤 몬스터도 잡지 않았기 때문에 아이템이 없다.
그렇기 때문에 모든 TIP을 무시한다. (기존 몬스터 난이도에 t를 더해줌)

그 몬스터 중에서 가장 낮은 난이도를 잡는 것이 현재 최선의 선택이라 할 수 있다.

이러한 과정은 몬스터의 넘버와 난이도를 우선순위 큐에 넣어주고, poll() 해주는 것으로 구현할 수 있다.

첫 번째 몬스터를 잡았으니 item을 얻게 되고, 그 item을 적용해 준다. 이때 당연히 우선순위 큐를 다시 구성한다면 시간 초과가 발생한다. 그냥 item을 적용해서 업데이트된 몬스터를 우선순위 큐에 넣어주면 된다. item을 적용한 몬스터는 난이도가 더 낮기 때문에 우선적으로 처리된다. (잡은 몬스터는 업데이트 해줄 필요가 없다. 그 몬스터를 잡은 환경에서는 그 아이템이 없었기 때문에 당연하다.)

중요한 점은 잡은 몬스터를 표시해야 중복되는 경우를 방지할 수 있다. 왜냐하면 우선순위 큐에는 같은 몬스터가 존재할 수 있고, 그중 가장 낮은 난이도의 몬스터가 우선적으로 처리됨으로써 이후 몬스터는 처리되면 안되기 때문이다.

이를 M마리 잡을 때까지 반복해 주고, 잡은 몬스터 중 가장 높은 난이도를 출력해 주면 된다.

소스 코드

import java.io.*;
import java.util.*;

class Tip {
    int b;
    long t;
    Tip(int b, long t) {
        this.b = b;
        this.t = t;
    }
}

class Monster implements Comparable<Monster> {
    int num;
    long lev;
    Monster(int num, long lev) {
        this.num = num;
        this.lev = lev;
    }
    
    @Override
    public int compareTo(Monster o) {
        if(this.lev < o.lev) {
            return -1;
        } else if(this.lev > o.lev) {
            return 1;
        }
        
        return 0;
    }
}

public class Main {
    static int N, M, p;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        long[] monsters = new long[N + 1];
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++) {
            monsters[i] = Integer.parseInt(st2.nextToken());
        }
        
        p = Integer.parseInt(br.readLine());
        ArrayList<ArrayList<Tip>> tipList = new ArrayList<>();
        for(int i=0; i<=N; i++) {
            tipList.add(new ArrayList<>());
        }
        
        for(int i=0; i<p; i++) {
            StringTokenizer st3 = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st3.nextToken());
            int b = Integer.parseInt(st3.nextToken());
            long t = Long.parseLong(st3.nextToken());
            tipList.get(a).add(new Tip(b, t));
        }
        
        System.out.println(answer(monsters, tipList));
    }
    
    static long answer(long[] monsters, ArrayList<ArrayList<Tip>> tipList) {
        //처음에는 아이템이 없음 그래서 모든 tip 무시
        for(int i=1; i<tipList.size(); i++) {
            for(int j=0; j<tipList.get(i).size(); j++) {
                int b = tipList.get(i).get(j).b;
                long t = tipList.get(i).get(j).t;
                monsters[b] += t;
            }
        }
        
        //우선 순위 큐에 다 넣어준다. 난이도만 넣어주는 것이 아닌 몬스터의 number도 같이 넣어준다.
        PriorityQueue<Monster> pq = new PriorityQueue<>();
        for(int i=1; i<monsters.length; i++) {
            pq.add(new Monster(i, monsters[i]));
        }
        //잡은 몬스터는 표시를 해줘야 중복을 방지할 수 있음
        boolean[] kill = new boolean[N + 1];
        
        long max = -1;
        for(int i=0; i<M; i++) {
            Monster mon = pq.poll();
            while(kill[mon.num]) {
                //죽이지 않은 몬스터를 찾을 때까지 반복
                mon = pq.poll();
            }
            kill[mon.num] = true;
            max = Math.max(max, mon.lev); //잡은 몬스터 중에서 최대 난이도로 업데이트
            //몬스터를 잡았기 때문에 mon.num아이템을 얻었다. 관련된 tip을 적용해줌
            
            for(int j=0; j<tipList.get(mon.num).size(); j++) {
                //이미 죽은 몬스터는 넣어주면 안됨
                int b = tipList.get(mon.num).get(j).b;
                long t = tipList.get(mon.num).get(j).t;
                if(!kill[b]) {
                    //아직 죽이지 않았다면 update
                    monsters[b] -= t;
                    pq.add(new Monster(b, monsters[b]));
                }
            }
        }
        return max;
    }
}