[백준 - 16678][GOLD 5][해설 X] - 모독 (JAVA)

문제 링크

---

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

 

문제

---

명예에 죽고 명예에 사는 나라 얼라이언스에는 1명의 왕과  N명의 국회의원이 있다. 각 N 명의 국회의원은 a1, a2, ..., aN 의 명예 점수를 갖고 있으며, 명예 점수가 양수인 한 그들은 국회의원을 계속 할 수 있다. 하지만 명예 점수가 0 이하가 되는 순간 그들은 국회의원에서 박탈당하며 오랫동안 비난의 대상이 된다.

국회의원들에게 밀려 권력이 없는 왕은 프로젝트 “Defile”을 설계해 모든 국회의원을 없애버릴려고 한다. 프로젝트 “Defile”은 다음과 같은 방식으로 작동한다. 

1.  모든 국회의원을 모독해서 각각의 명예 점수를 1씩 감소시킨다.
2.  (1)로 인해 1명이라도 국회의원에서 박탈당한 사람이 발생했다면 국민들의 분노를 이용해 (1)로 돌아간다.
3.  (1)에 의해 국회의원에서 박탈당한 사람이 없다면 프로젝트를 종료한다.

프로젝트 자체가 명예롭지 못한 행동이기에 왕은 단 1번의 “Defile”을 실행해 모든 국회의원을 박탈시키고 싶다. 이를 위해 그는 전문해커집단 “제이나”에서 해커를 여러 명 고용했다. “제이나”에 소속된 각 해커는 사이버 상에 있는 흑역사를 추적해 국회의원 1명의 명예를 1만큼 감소시킬 수 있다. 이 역시 명예롭지 못하기에 왕은 최소한의 해커를 고용하려고 한다. 과연 왕은 최소 몇 명의 해커를 고용해야 할까? 

 

입력

---

첫 번째 줄에는 국회의원의 명수 N이 주어진다. (1 ≤ N ≤ 100,000)

이후 두 번째 줄부터 N개의 줄에 걸쳐 국회의원의 명예 점수가 주어지며, 그중 i번째 줄에는 i번째 국회의원의 명예점수인 정수 ai 가 주어진다. (1 ≤ ai ≤ 100,000)

 

출력

---

첫 번째 줄에 프로젝트를 성공시키기 위해 최소한으로 고용해야하는 해커의 수를 출력한다.

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for(int i=0;i<N;i++){
            pq.add(Integer.parseInt(br.readLine()));
        }

        int damage = 1;
        long cost = 0;

        //가장 작은것 부터 모독 판별
        while(!pq.isEmpty()){
            int curr = pq.poll();

            //만약 현재 데미지보다 작으면 이전 데미지로도 평판이 0이기 때문에 이미 박탈당한 국회의원이다.
            if(damage > curr){
                continue;
            }

            //부족한 평판만큼 해커를 투입한다.
            cost += curr - damage;
            damage++;
        }

        System.out.println(cost);
    }
}

 

 

실행 결과

---

 

팁

---

• 중복이 되는 지점을 어떻게 처리해야할지 고민하자