[JAVA] 백준 4228 : The Dragon of Loowater

백준 4228 : The Dragon of Loowater

 

문제 링크:

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

4228번: The Dragon of Loowater

 

 

문제 내용:

(요약) 머리가 n개가 달린 드래곤이 Loowater 왕국에 쳐들어왔다. 드래곤을 처치하기 위해서는 m명의 기사들이 머리를 모두 베어야한다. 이때, 기사의 키가 드래곤 머리의 지름보다 크거나 같아야 머리를 벨 수 있다고 한다. 한 사람당 머리 하나만을 벨 수 있으며 머리를 벤다면 자신의 키만큼 gold coin을 얻게 된다.

그러나 Loowater 왕국의 왕은 최근에 공원을 만드느라 많은 돈을 써서 최대한 적은 돈으로 드래곤을 처치하고 싶다. 왕이 기사들에게 지불해야할 최소 금액은 얼마일까?

 

1<= n, m <= 20000

첫 줄에 n과 m이 주어지고

두번째 줄 부터는 드래곤의 머리 지름 n개와 기사의 키 m개가 주어진다.

 

n=0, m=0 이라면 프로그램 종료

 

ex)

2 3 //n=2, m=3

5

4

7

8

4

=> 11

 

 

Idea:

1. 우선순위 큐(Priority Queue)를 사용하여 입력받는 드래곤 머리의 지름과 기사의 키를 오름차순으로 기록한다.
2. 큐를 통해 드래곤과 기사들을 비교하며 기사가 벨 수 있는 경우 돈을 더한다(탐욕 알고리즘, Greedy Algorithm).
3. 드래곤의 큐나 기사의 큐에 데이터가 없다면 비교를 종료한다.

 

Priority Queue

• add(int) : 큐에 데이터 추가
• isEmpty() : 큐에 내용이 비었는지를 판단
• peek() : 상단 데이터 읽기
• poll() : 상단 데이터 제거
• clear() : 큐의 내용 지우기

 

 

Code:

import java.util.*;
 
public class Q_4228{
    static void doom() {
        System.out.println("Loowater is doomed!");
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //우선순위 큐
        PriorityQueue<Integer> dragon = new PriorityQueue<Integer>();
        PriorityQueue<Integer> knight = new PriorityQueue<Integer>();
        
        int n, m, tmp, coin;
        while(true) {
            coin=0;
            n=sc.nextInt();//드래곤
            m=sc.nextInt();//기사
            if(n==0 && m==0) break;
            
            //dragon의 머리크기
            for(int i=0;i<n;i++) {
                tmp=sc.nextInt();
                dragon.add(tmp);
            }
            
            //knight의 키
            for(int i=0;i<m;i++) {
                tmp=sc.nextInt();
                knight.add(tmp);
            }
            
            /*결과*/
            //드래곤의 머리수가 기사보다 많은 경우
            //실패!
            if(n>m) {
                doom();
                continue;
            }
            //드래곤의 머리수보다 기사가 더 많거나 같을 경우
            else {
                while(true) {
                    //큐에 드래곤과 기사가 없거나 드래곤의 머리가 없는 경우
                    //성공!
                    if(knight.isEmpty()&&dragon.isEmpty() || dragon.isEmpty()) {
                        System.out.println(coin);
                        break;
                    }
                    //큐에 기사가 없는 경우
                    //실패!
                    else if(knight.isEmpty()) {
                        doom();
                        break;
                    }
                    //드래곤 머리의 지름이 기사의 키보다 작거나 같은 경우
                    //토벌 가능.
                    if(dragon.peek() <= knight.peek()) {
                        coin+=knight.poll();
                        dragon.poll();
                    }
                    //드래곤 머리의 지름이 기사의 키보다 큰 경우
                    //토벌 불가능. 다음 기사로
                    else {
                        knight.poll();
                    }
                }
            }
            //큐의 내용 비우기
            dragon.clear();
            knight.clear();
        }
    }
}