자바 - 백준 2212 / 센서

백준 2212 센서
골드5

구현 방법

범위을 봤을 때 완전 탐색은 시간초과 날게 뻔했다.
그래서 바로 매개변수 탐색을 생각했다. 하지만 최소 거리마다 구간을 나누어서 확인해줘야하는데
이런 방식으로 해도 시간초과 문제를 해결할 수 없다고 판단했다. 결국엔 완전탐색과 같은 방법이 된다.
그럼 dp인가? 생각했다. 임의의 두 센서의 구간 차이를 저장하고 이를 바탕으로 최소 거리를 구하면 되지 않을까? 생각했다.
하지만 반복되는 규칙이 보이지 않아 아니라고 판단했다.
결국 위 세 방식 모두 최후에는 구간을 나누는 경우의 수를 모두 생각해본다는 완전탐색이 되어버렸다!!

그럼 이문제는 그리디겠다 라는 생각이 들었다.
그러나 로직이 떠오르지 않아 힌트를 보고 풀었다. 너무 아쉽...


구현방식

1. 먼저 센서 좌표를 배열로 저장하고 오름차순 정렬한다.
2. 만약 집중국 개수 >= 센서 좌표 개수인 경우 센서마다 집중국을 생성하면 되므로 최소 거리는 0이 된다. => 끝
3. 만약 집중국 개수 < 센서 좌표인 경우, 인접 센서 좌표별 거리 차이를 구해 배열로 저장한다.
4. 인접 센서 좌표별 거리 차이 배열을 오름차순 정렬한다.
5. (센서 개수 - 집중국 개수) 만큼의 인접 센서 좌표별 거리 차이를 더해준다.
   이유는 좌표별 거리 차이가 많이 나는 센서 좌표의 경우 집중국을 설치해서 거리를 최소로 만들어야 하기 때문이다.

코드

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

/**
 * 백준 2212
 * 센서
 * 골드5
 * https://www.acmicpc.net/problem/2212
 */
public class Boj2212 {

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

        int N = Integer.parseInt(br.readLine());
        int K = Integer.parseInt(br.readLine());

        if(N <= K)
            System.out.println(0);
        else {
            int[] censor = new int[N];
            st = new StringTokenizer(br.readLine());
            for(int i = 0; i < N; i++)
                censor[i] = Integer.parseInt(st.nextToken());

            Arrays.sort(censor);
            int[] dif = new int[N - 1];

            for(int i = 0; i < N - 1; i++)
                dif[i] = censor[i + 1] - censor[i];

            Arrays.sort(dif);

            int answer = 0;
            for (int i = 0; i < N - K; i++) {
                answer += dif[i];
            }

            System.out.println(answer);
        }
    }
}

 

느낀 점

그리디 연습 많이 하자^^