백준 16678 자바 - 모독 (BOJ 16678 JAVA)

문제 : boj16678

 

 

1. 문제 이해

  결국 단 1번의 Defile로 모두 박탈시키려면 모든 의원의 명예를 1부터 차츰차츰 상승하는 계단형식으로 만들면 된다. 즉, 모든 의원의 명예가 낮은 명예부터 봤을 때 2이상 차이가 나지 않게 하면 된고, 이렇게 만들 때 최소한만 감소시켜서 진행해야 한다.

 

 

2. 문제 풀이

  1부터 n까지 확인하면서 해당 값을 한명씩 무조건 가지도록 명예를 깎는다면 모든 명예값이 2이상 차이나지 않을 수 있다. 단순히 생각해도 더 낮은 숫자를 만들기 위해서는 애초에 명예가 낮은 의원의 명예를 깎는것이 더 최소한의 횟수로 만들 수 있을 것이다.

 

  따라서 우선 입력으로 들어온 값을 오름차순으로 정렬해보자. 그리고 1부터 1개씩 증가시키며 해당 값에 한명 이상 매칭시켜보자. 예를들어 '예제 입력1'은 다음과 같이 처리할 수 있다. '7 3 6 2 4'로 들어온 입력을 우선 정렬한다. 그 후 1번의 Defile로 모두 박탈시키려면 1부터 차례대로 매칭시키면 된다(정렬을 하지 않으면 최소수치가 아니게 된다.). 이하 그림에서 '-'값들을 모두 합쳐보면 답인 7이 나오게 됨을 알 수 있다.

 

  그럼 입력이 '4 3 1 4 2'인 경우도 봐보자. 정렬을 하면 '1 2 3 4 4'가 되므로 처음부터 한번의 Defile로 모두 박탈 가능하다.

 

  이번엔 '1 1 1 1 5'를 확인해보자. 이 경우 '1'의 명예를 가진 의원의 명예를 높힐 방법은 없으므로, '5'의 값을 '2'로 낮춰야 한다. 또한 '1'의 값들은 처음에 이미 제거가 되므로 신경쓸 필요가 없다.

 

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;
import java.util.Arrays;

public class Main extends FastInput {
    private void solution() throws Exception {
        int n = nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = nextInt();
        Arrays.sort(arr);

        int target = 1;
        long sum = 0;
        for (int i = 0; i < n; i++) {
            if(arr[i] < target) continue;
            sum += arr[i]-target;
            arr[i] = target++;
        }
        System.out.println(sum);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}