2212번 센서

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

k개의 집중국을 세울 때, (k-1)개의 빈 공간이 생긴다.

집중국을 점으로 생각하고, 종이에 그려보면서 생각하자.

그럼 k-1개의 빈 공간이(길이가) 가장 클 때 우리가 원하는 각 집중국의 수신 영역 길이(빈 공간을 제외한 나머지 공간(길이))의 합을 구할 수 있다.

즉, 길이가 가장 큰 것을 빈 공간으로 하고 이것을 덧셈에서 빼주면 된다.

길이를 담은 d vector의 size()에서 (k-1)번 덜 실행하여 누적 덧셈을 하면 된다.

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int n, k, ans = 0;
    static Vector<Integer> v = new Vector<Integer>();
    static Vector<info> d = new Vector<info>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        n = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());
 
        st = new StringTokenizer(br.readLine());
        
        for(int i=0; i<n; i++) {
            int input = Integer.parseInt(st.nextToken());    
            v.add(input);
        }
        
        Collections.sort(v);
        
        for(int i=0; i<n - 1; i++) {
            d.add(new info(v.get(i + 1) - v.get(i), v.get(i), v.get(i+1)));
        }
        
        Collections.sort(d, new Comparator<info>(){
            public int compare(info a, info b) {
                return Integer.compare(a.dist, b.dist);
            }
        });
        
        for(int i=0; i<d.size() - k + 1; i++) {
            ans += d.get(i).dist;
        }
        
        bw.write(String.valueOf(ans) + "\n");
        bw.flush();
        bw.close();
    }
}
 
class info {
    int dist, s, e;
    info(int dist, int s, int e) {
        this.dist = dist;
        this.s = s;
        this.e = e;
    }
}