[BaekJoon] 2212 센서 (Java)

🔗 문제 링크

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

📝 문제풀이 방법

N개의 센서들 사이에 M개의 집중국을 설치하여 M개의 집단을 만들었을 때 각각 집중국들이 커버하는 거리의 최솟값을 구하는 문제이다.

하나의 집중국들이 커버하는 거리는 해당 집중국이 포함된 집합의 센서들사이의 거리의 합과 같다고 할 수 있다.

그래서 집중국들이 커버하는 거리가 최소가 되려면 센서 사이의 거리가 가장 긴 거리를 나누어 M개의 집합을 만들면 된다.

즉, 센서사이의 거리를 구하여 정렬한 후 가장 길이가 긴 M-1개의 값을 0으로 변경해주고 센서사이의 거리의 합을 구하면 최종 결과가 된다.

👨🏻‍💻 작성한 코드

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

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		
       		// 센서보다 집중국이 더 많은 경우 거리는 0 
		if (M >= N) {
			System.out.println(0);
			System.exit(0);
		}
		
		int[] sensor = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i=0; i<N; i++) {
			sensor[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(sensor);

		// sensor사이의 거리 계산
		Integer[] sensorDistance = new Integer[N-1]; // sensor사이의 거리
		for (int i=0; i<N-1; i++) {
			sensorDistance[i] = sensor[i+1] - sensor[i];
		}
		Arrays.sort(sensorDistance, Collections.reverseOrder());
		
		// 가장 긴 거리 M-1개를 0으로 초기화(해당 위치에 기지국을 설치하기 때문)
		for (int i=0; i<M-1; i++) {
			sensorDistance[i] = 0;
		}
		
		// 최종 길이 구하기
		int result = 0;
		for (int i=0; i<N-1; i++) {
			result += sensorDistance[i];
		}
		
		System.out.println(result);	
	}
}