99클럽 코테 스터디 18일차 TIL (미들러): [백준][Java] 2212 센서 - 골드5

 

문제 보기

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

 

 

풀이

처음엔 지문이 이해되지 않았다.

그래서 시간을 많이 소비하였다.

 

예제 1번을 우선 오름차순으로 정렬해보자.

 

우선 처음 나오는 센서인 1번에 집중국이 하나 있다고 생각해보자.

전체 길이는 9가 된다.

 

그리고 집중국은 두 곳 놓을 수 있다.

직관적으로 생각해서 어디에 놓으면 좋을까?

 

나라면 6번에 놓을 것 같다.

3 - 1 = 2, 9 - 6 = 3

총거리는 5가 된다.

 

사실 나는 문제를 제대로 이해하지 못해서 아래와 같은 상황을 생각했었으나 집중국으로부터 떨어진 정도(반지름의 길이)가 아니라 총거리를 구하는 것이었다.

 

어찌 됐든 6번에 놓으면 좋겠다는 건 어떤 생각을 해서 결론이 그렇게 나왔던 걸까?

아무래도 3~6 거리가 3이나 되기 때문일 것이다.

이렇게 센서와 센서 사이의 거리가 크면 한 번 끊고 다음 센서에 집중국을 설치하는 게 좋다는 것이다.

 

int[] arr = new int[N];
for(int i = 0; i < N; i++) {
  arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);

int[] dist = new int[N-1];
for(int i = 0; i < N-1; i++) {
  dist[i] = arr[i+1] - arr[i];
}
Arrays.sort(dist);

그럼 이제 핵심 코드를 살펴보자.

센서의 위치를 담은 배열 arr을 오름차순으로 정렬하는 것이 선행되어야 한다.

그리고 센서와 센서 사이의 거리를 담은 배열도 필요하다.

이 거리도 오름차순으로 정렬해 주자.

 

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

이제 마지막으로 총거리를 구할 것이다.

제일 짧은 거리부터 N - K까지만 구하면 된다!

왜냐하면 집중국을 설치함으로써 제일 긴 길이 K - 1개는 없애 버릴 것이기 때문이다.

N-1 - (K-1)을 정리한 것이다.

 

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
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));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());
    int K = Integer.parseInt(st.nextToken());
    st = new StringTokenizer(br.readLine());
    int[] arr = new int[N];
    for(int i = 0; i < N; i++) {
      arr[i] = Integer.parseInt(st.nextToken());
    }
    Arrays.sort(arr);

    int[] dist = new int[N-1];
    for(int i = 0; i < N-1; i++) {
      dist[i] = arr[i+1] - arr[i];
    }
    Arrays.sort(dist);

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

    bw.write(sum + "\n");

    bw.flush();
    bw.close();
  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Gold/2212.%E2%80%85%EC%84%BC%EC%84%9C

CodingTest_AutoSave/백준/Gold/2212. 센서 at main · MetroDefro/CodingTest_AutoSave