[자바/백준 골드5] #2212 센서

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

🔒 골드5 - #2212 센서

 

 

📌 테스트케이스 추가 힌트

6
2
1 6 3 3 4 3

= 3

9
3
1 3 5 5 8 9 10 11 16

= 7

 

 

✍️ 풀이법

 

문제를 보자마자, 정렬은 해 놓아야 한다고 생각했다.

그 후, 임의로 몇 개의 테스트케이스를 만들면서 푸는 방법을 생각해 보았다.

 

먼저 첫번째 테스트 케이스

6
2
1 6 3 3 4 3

= 3

 

이해를 위해 그림으로 나타내면 다음 사진과 같고,

집중국 2개가 위치해야 될 곳은 다음 사진과 같다.

위 그림을 보면 알 수 있는 것은

 

    A) 집중국은 센서 위에 위치해야 한다.

        - 센서 위에 있어야 하나의 센서라도 감지 영역을 0으로 만들 수 있다.

 

    B) 집중국의 개수대로 센서 뭉텅이가 생긴다.

        - 위 그림으로 예를 들면,   [1, 3, 3, 3, 4]  /  [ 6]   두 개의 뭉텅이로 나누어졌다고 생각하면 된다.

 

 

 

센서가 뭉텅이로 나누어진다면, 센서 사이의 거리가 가장 먼 곳을 기점으로 뭉텅이를 나누어야 한다.

위 테스트 케이스의 센서 사이의 거리는 다음과 같다.

여기에 집중국이 2개 설치 된다면, 센서 사이의 거리가 먼 4와 6을 기점으로 뭉텅이가 2개 생기게 되고,

두 뭉텅이 사이의 거리는 측정할 필요가 없어진다.

이후 나머지 센서 사이의 거리를 더하면, 집중국이 감지할 영역이 구해진다.

2 + 1 = 3

 

 

 

 

마찬가지로, 두번째 테스트 케이스를 그려보면 다음 그림과 같아진다.

세 개의 집중국 이기 때문에, 세 개의 뭉텅이로 나누어지고, 뭉텅이 사이가 가장 긴 곳을 기점으로 뭉텅이가 나누어진다.

2 + 2 + 1 + 1 + 1 = 7

 

 

 

결국 풀이는,

    1. 센서를 좌표 순으로 정렬한다.

    2. 센서와 센서 사이의 거리를 구한다.

    3. 센서 사이의 거리가 큰 순으로 ( 집중국 수 - 1 ) 만큼 지운다. 

        ( = 뭉텅이를 나누고 뭉텅이 사이의 거리를 지운다.)

    4. 남은 센서 사이의 거리를 합한다.

 

 

 

 

 

🗝️ 풀이

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class baekjoon2212 {

    static List<Integer> point = new ArrayList<>();
    static List<Integer> distanceOfPoint = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int K = sc.nextInt();

        for (int testCase = 0; testCase < N; testCase++) {
            point.add(sc.nextInt());
        }

        solve(K);
    }

    public static void solve(int K) {
        Collections.sort(point);
        setDistanceOfPoint();
        calMinDistance(K);
    }

    private static void calMinDistance(int k) {
        int sum = 0;

        Collections.sort(distanceOfPoint);
        for (int i=0; i< distanceOfPoint.size() - k + 1; i++){
            sum += distanceOfPoint.get(i);
        }
        System.out.println(sum);
    }

    private static void setDistanceOfPoint() {
        for (int i = 0; i < point.size() - 1; i++) {
            distanceOfPoint.add(point.get(i + 1) - point.get(i));
        }
    }
}