[백준] 2212 센서 (JAVA) - 풀이

문제 분석

• 직선의 고속도로에 원점을 기점으로 N개의 센서가 설치되어 있음
• N개의 센서가 적어도 1개의 집중국과 통신되어야 하고, 최대 K개의 집중국을 세울 수 있음
• 각 집중국의 수신 가능 영역 길이(0 이상) 합의 최소값을 구하기

 

의사 결정

• K개의 집중국을 세우면, 집중국 사이의 빈공간이 K-1개가 생깁니다.
• 센서 사이의 거리를 내림차순하여 정렬합니다.
• 큰 거리부터 K-1개의 공간을 제외하고, 나머지 공간을 모두 더하는 방식을 사용했습니다.

 

코드 구현

1. 센서와 집중국의 개수, 센서 좌표 입력 받기

각 센서의 위치는 배열에 저장했습니다.

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine()); // 센서 수
		int K = Integer.parseInt(br.readLine()); // 집중국 수
		
		int[] sensors = new int[N]; // 센서 좌표 저장
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0 ; i<N ; i++) {
			sensors[i] = Integer.parseInt(st.nextToken());
		}

 

 

2. 각 센서 간의 거리 계산 및 저장

센서 좌표 배열을 오름차순으로 정렬했습니다.

 

센서 간 거리는 N-1개이기 때문에 이에 맞게 배열 크기를 저장하고, 이중 for문 사용해 센서 간 거리를 계산했습니다.

		Arrays.sort(sensors); // 센서 좌표 오름차순 정렬
		
		Integer[] distance = new Integer[N-1]; // 각 센서 사이 거리 저장
		for(int i=1 ; i<N ; i++) {
			for(int j=i-1 ; j<i ; j++) {
				distance[j] = sensors[i] - sensors[j];
			}
		}

 

 

3. 남은 거리 계산

센서 간의 거리 배열을 내림차순으로 정렬하여, 가장 큰 거리들부터 제외할 수 있도록 했습니다.

 

해당 배열을 저장할 때 0번째부터 저장했기 때문에, K-2개까지 제외하고, K-1개부터 더해서 출력했습니다.

		Arrays.sort(distance, Collections.reverseOrder()); // 센서 사이의 거리를 내림차순 정렬
		
		int sum = 0;
		for(int i=K-1 ; i<N-1 ; i++) { // 각 거리 sum에 저장
			sum += distance[i];
		}
		
		System.out.print(sum);

 

 

 

전체 코드

package Beakjoon.gold;
import java.util.*;
import java.io.*;
public class bj2212 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine()); // 센서 수
		int K = Integer.parseInt(br.readLine()); // 집중국 수
		
		int[] sensors = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0 ; i<N ; i++) {
			sensors[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(sensors); // 센서의 위치를 오름차순 정렬
		
		Integer[] distance = new Integer[N-1]; // 각 센서 사이 거리 
		for(int i=1 ; i<N ; i++) {
			for(int j=i-1 ; j<i ; j++) {
				distance[j] = sensors[i] - sensors[j];
			}
		}
		
		Arrays.sort(distance, Collections.reverseOrder()); // 센서 사이의 거리를 내림차순 정렬
		
		int sum = 0;
		for(int i=K-1 ; i<N-1 ; i++) {
			sum += distance[i];
		}
		
		System.out.print(sum);
	}
}