[백준, 자바, 2212번] 센서

풀이

• 해당 문제는 뭔가 문제부터 이해가 어려웠고, 
• 마지막 결과도 스스로 해결하지 못해서 여러 글을 참고하여 이해.
• 우선 해당 문제는
• N개의 센서를 K개의 집중국 만으로 체크를 할 때,
• 각각의 집중국으로 확인되는 센서의 차의 합이 최소가 되도록 만드는 문제로 이해할 수 있을 듯하다.
• 그래서 처음에는 입력되는 센서를 정렬 후
• 첫 값과 마지막 값을 뺀 차를 K로 나누어 임의의 구간을 찾아 해결하고자 했는데
• TC결과만 정답이고, 완전한 정답을 찾지는 못하여 여러 글을 보며 이해함.
• 다른 글을 보니 각 센서간 거리의 차를 구한 배열을 구하고,
• 이를 내림차순으로 정렬한 뒤, K-1부터 끝까지 더한 합을 결과로 제출.
• 하지만 이해가 가지 않았음...
• 왜 센서간 거리의 차를 구하고, 왜 K-1부터 더하는 거지?
• 그래서 다시 조사하며, 이해를 해보니까
• 거리의 차가 큰 구간을 기점으로 집중국을 분리하여 설치해야하니깐
• 내림차순을 진행한 거고,
• K-1부터 더하는 이유는 K개의 집중국을 설치하게 되면 사이의 공간이
• K-1개가 생기기에 K-1부터 더하여 해결한다는 의미가 됨.

 

# 정답 코드

import java.io.*;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class _2212 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int K = Integer.parseInt(br.readLine());
        int[] li = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++) li[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(li);
        Integer[] diff = new Integer[N-1];
        for (int i=0; i<N-1; i++) diff[i] = li[i+1]-li[i];
        Arrays.sort(diff, Collections.reverseOrder());
        // 즉, 센서간 차이를 내림차순으로 정렬 후, 집중국 개수 -1 부터 끝까지 더하면 결과로 나옴
        // 이유는 센서간 차이가 큰 공간을 기준으로, 집중국을 구분해야 최소의 합이 나오기 때문.
        int result = 0;
        for (int i=K-1; i<N-1; i++) result += diff[i];
        System.out.println(result);
    }
}

 

# 실패 코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long K = Integer.parseInt(br.readLine());
        int[] li = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++) li[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(li);
        int dis = (li[N-1]-li[0])%K>K/2?(li[N-1]-li[0])/(int)K:(li[N-1]-li[0])/(int)K-1;
        int s = li[0];
        int e = li[0]+dis;
        int result = 0;

        for (int i=1; i<N; i++) {
            if (s<=li[i] && li[i]<=e) continue;
            else {
                result += li[i-1]-s;
                s = li[i];
                e = s+dis;
            }
        }

        if (e>=li[N-1]) result += li[N-1]-s;
        System.out.println(result);
    }
}