[백준] 2212 센서 - 그리디 JAVA

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

2212번: 센서

코드설명

그리디 문제입니다.

 

 

입력예시로 설명해보겠습니다.

입력값
6
2
1 6 9 3 6 7

문제를 읽다보면, 원점으로부터의 정수거리의 위치에 놓여있습니다.

이 조건을 통해 오름차순 정렬을 통해 정수의 순서를 봐야합니다.

센서 위치 오름차순 정렬
1 3 6 6 7 9

• 센서가 같은 위치에 2개 있는 경우가 있습니다. 
• 이떄, 센서의 개수는 중요하지 않기에 HashSet으로 중복을 사라지게 합니다.

센서 위치 오름차순 정렬
1 3 6 7 9

이제 집중국 2개를 사용해서 집중국의 수신가능영역길이의 최소값을 구해야합니다.

문제 이해가 어려운데,

예로들어보면,

(1, 3) -> 수신가능영역 : 2

(6, 7, 9) -> 수신가능영역 : 3

으로 이해하시면 됩니다.

 

이제 각 센서들의 위치 차이를 구합니다.

센서 위치 차이
2 3 1 2

• 우리는 센서 위치 차이가 최소인 것을 쉽게 구하기위해 오름차순으로 정렬합니다.

센서 위치 차이 오름차순 정렬
1 2 2 3

• 이제 여기서 정답을 먼저 말해보면 앞의 2개를 더한 1 + 2 = 3 이 정답입니다.

여기서 우리가 구한 차이의 개수들은 N - 1 개입니다. (1 3 6 7 9 )

위의 예시에서는 N = 5이므로 차이의 개수는 4개입니다. ( 1 2 2 3 )

 

우리가 구하고자하는 그룹의 개수는 2개입니다. 여기서 2개란, 집중국의 개수입니다.

( 문제조건에서 K = 2 이라고 나와있습니다. )

1 2 2 3 이 있을때 2개의 그룹으로 나눌려면, 1개의 구분선이 있으면 가능합니다.

예시로는, 1 3 ★ 6 7 9   (여기서 별이 구분선 입니다. ) 

보시다시피, 2개의 그룹을 만들려면 1개의 구분선이 필요한걸 알 수 있습니다. 즉, K - 1 개의 구분선이 필요한 것입니다.

 

문제에서 구분선을 구하기 위해서는 우리가 구한

센서 위치 차이 오름차순 정렬
1 2 2 3

• 4 개 중에서 3개를 정하면, 그게 최소의 비용일 것 입니다. ( 남은 1개는 구분선이 되어서 더해지지 않습니다. )

즉, 위의 4 길이의 차이배열에서 결국 최소값의 3개만 선택한다는 의미입니다.

수학적으로 보면,

키차이의 개수를 구하면, N - 1 개입니다. (5개의 입력값에서는 4개의 차이의 배열이 나옵니다.)

구분선의 개수를 구하면, K - 1 개입니다. (2개의 그룹을 가지려면, 1개의 구분선으로 그룹을 나눕니다.)

즉, (N - 1) - ( K - 1 ) 개. N - K 개의 차이배열만 더해주면 해당 값이 최소입니다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	
	public static int N,K;
	public static int[] arr;
	public static int[] arr_diff;
	public static HashSet<Integer> hashset = new HashSet<>();
	public static int answer =0 ;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	
    	st = new StringTokenizer(br.readLine());
    	K = Integer.parseInt(st.nextToken());
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		hashset.add(Integer.parseInt(st.nextToken()));
    	}
    	
    	int newN = hashset.size();
    	arr = new int[newN];
    	arr_diff = new int[newN - 1];
    	
    	int index = 0;
    	for(int a : hashset) {
    		arr[index++] = a;  
    	}
    	
    	Arrays.sort(arr);
    	for(int i=0;i<newN-1;i++) {
    		arr_diff[i] = Math.abs(arr[i+1] - arr[i]);    		
    	}
    	
    	Arrays.sort(arr_diff);
    	
    	for(int i=0;i<newN-K;i++) {
    		
    		if(arr_diff[i] == 0)continue;
    		answer += arr_diff[i];
    	}
    	System.out.println(answer);
    }
}