99클럽 코테 스터디 18일차 TIL 그리디(센서)

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

아 오늘은 아이디어를 떠올리는 게 쫌 어려웠다,,

처음엔 이전 집중국과의 거리와 다음 센서 사이의 거리를 비교해서 더 이득인 경우를 택하는 형식으로 구현했는데,

이 경우 집중국의 개수는 맞았지만 거리를 계산할 때 거리의 최솟값을 만족하지 못했다..

그래서 고민고민하다가 구글링으로 스리슬쩍 구경했느데

와 역으로 제일 먼 거리를 빼면 되는 아주 간단한 아이디어 였다,,

그래서 결론은

 

<아이디어>

1. 받은 센서의 좌표를 오름차순으로 정렬한다.

2. 센서 사이의 거리를 구해서 배열에 저장한다.

3. 이 센서 사이의 거리를 정렬해서 가장 거리가 먼 경우를 k-1 개 제외한 거리의 값을 더하면 최솟값이다.

(k=2 일 때, 1(k-1)번 나누면 2그룹으로 나뉘고 이 2그룹에 집중국을 설치)

 

<제출 코드>

package Study.Week03;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Day18_BOJ_2212_센서 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int k = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) arr[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(arr);
        int[] dis = new int[n-1];
        for(int i=0; i<n-1; i++) {
            dis[i] = arr[i+1] - arr[i];
        }
        Arrays.sort(dis);
        int cnt = 0;
        int ans = 0;
        for(int i=n-1; i>=0; i--){
            if(cnt < k) {
                cnt++;
                continue;
            }
            else {
                ans += dis[i];
            }
        }
        System.out.println(ans);
    }
}