[백준] 2212 센서 - JAVA

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

 

2212번: 센서

 

❔문제가 이해가 잘 되지 않았다.. 질문 게시판을 참고하여 이해한 결과..

주어진 n개의 센서를 집중국의 갯수 k 만큼 집합, 즉 묶으면 된다. 예를 들어 예제 1번에서는 [1,3] [6,6,7,9] 2개의 구간으로 묶으면 범위가 2+3=5 로 최소가 된다. 

 

알고리즘

• "최소" 합을 구해야 하기 때문에 센서를 모두 설치하여 가장 거리차이가 많이 나는 부분을 제거한다.  
• 단, 센서의 갯수보다 집중국의 갯수가 더 많거나 같으면 1 집중국 당 1 센서를 맡으면 되기 때문에 최소합은 0이다. 

 

---

 

구현 과정

• sensor[] : 주어진 N개의 센서의 좌표를 저장할 배열 
• diff[] : i번째 센서와 i+1번째의 센서의 거리를 저장할 배열 , 크기 = N-1

 

1. 주어진 센서의 좌표를 sensor 배열에 저장 한 후, 오름차순으로 정렬한다. 

 

2. 만약 집중국의 갯수가 센서의 갯수보다 많거나 같다면 1을 출력하고 종료한다. 

 

3. sensor 배열에서 sensor[i] 와 sensor[i+1] 간의 거리를 구해 diff 배열에 저장한다. 

 

4. diff 배열을 오름차순으로 정렬하여, diff의 길이-K-1 인덱스까지의 합을 더한다. K개의 묶음을 만들기 위해서는 센서간의 연결되어 있는 거리 중 (K-1) 개를 끊어야 하기 때문이다. 

 

 

🔎예제 입력 2번 

• sensor 배열에 저장 후 정렬 

3

6

7

8

10

12

14

15

18

20

 

• 각 센서간의 거리를 diff 배열에 저장 

3

1

1

2

2

2

1

3

2

 

• 오름차순 정렬 

1

1

1

2

2

2

2

3

3

 

• 집중국 5개, 5개의 집합으로 만들기 위해서는 주어진 9개의 연결 중, 4개를 끊어야 한다. 

1

1

1

2

2

2

2

3

3

즉, 최소합을 구해야 하기 때문에 거리가 큰 것들은 포함 시키지 않기 위해 오름차순 정렬 후 앞에서 부터 더한 것. 

 

 

 

---

 

소스 코드 

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

public class Solution_BaekJoon_2212 {
	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());//집중국의 갯수 
		
		int[] sensor= new int[N]; 
		st= new StringTokenizer(br.readLine(), " ");
		
		for(int i=0; i<N; i++) {
			sensor[i]= Integer.parseInt(st.nextToken()); 
		}
		
		//센서보다 집중국이 더 많거나 같으면, 집중국 하나가 센서 하나씩 맡으면 됨 
		if(K>=N) {
			System.out.println(0);
			System.exit(0);
		}
		
		Arrays.sort(sensor);
		
		int[] diff= new int[N-1]; //각 센서간의 거리 차이 
		for(int i=0; i<diff.length; i++) {
			diff[i] = sensor[i+1]-sensor[i]; 
		}
		
		Arrays.sort(diff);
		int sum=0; 
		//만약 집중국이 2개라면, 주어진 센서를 2분류로 나누어야 한다. 그럼 집중국 이어진 diff 중에 하나를 끊어야함 (젤 큰값) 
		for(int i=0; i<diff.length-(K-1); i++) {
			sum+=diff[i];
		}
		
        System.out.println(sum);

	}//end of main 
}//end of class