[java] 백준 2212 센서

문제

2212번: 센서 (acmicpc.net)

2212번: 센서

문제 이해를 잘 해야한다. 처음에 센서들의 거리 누적합을 구하는줄 알고 잘못된 접근을 하였다.

센서의 개수 N , 집중국의 개수 K 가 주어진다.

먄약 K == N 이면 각 집중국마다 센서가 있음으로 거리합이 0 이 된다 .

만약 K == 1 이면, 집중국은 센서의 거리 범위 ( i.. j ) 안에 놓기만 하면 j - i 거리합이 된다.

 

K > 1 이면, 이때부터 잘 봐야한다.

1. 센서의 거리합을 최소화 해야 하기 때문에 우선 중복을 제외한 센서들을 오름차순 정렬 한다. ,
2. 그런 다음 센서들간의 거리차를 저장한다. 거리차는 ( N - 1 ) 개이다 .
3. 거리차 배열을 정렬하고, 거리차 배열의 길이 = len
4. len - (k-1) 까지의 누적합을 구한다.

 

다음사진은 문제 이해하는데 도움이 될까바 첨부한다.

코드

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

public class Main {
    static int res = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        FastReader fr = new FastReader();
        int N = fr.nextInt();
        int K = fr.nextInt();
        ArrayList<Integer> sensorL = new ArrayList<>();
        ArrayList<Integer> dist = new ArrayList<>();

        for(int i = 0 ; i< N ;i++){
            sensorL.add(fr.nextInt());
        }
        Collections.sort(sensorL); //오름차순 정렬
        for(int i = 1 ; i< N ;i++){
            if(sensorL.get(i) != sensorL.get(i-1)) {
                dist.add(sensorL.get(i) - sensorL.get(i-1)); // 센서 거리의 차 저장
            }
        }
        Collections.sort(dist);
        int ans = 0 ;
        for(int i = 0 ;i< dist.size() - (K-1) ; i++){
            ans += dist.get(i);
        }
        //System.out.println(dist);
        System.out.println(ans);
    }

    public static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}