백준 2212 센서 java

그리디 알고리즘

전수민

Nov 21, 2025

TABLE OF CONTENTS

1. 문제에 대하여 📦

문제 링크: https://www.acmicpc.net/problem/2212

직선 상에 센서가 N개 존재한다. K개의 집중국이 존재하고, 각 집중국은 수신 영역을 늘리거나 좁혀서 센서의 내용물을 감지할 수 있다.
모든 센서를 감지하려고 할 때 필요한 전체 수신영역의 합의 최소값은?

(1) 조건 분석 📊

문제 가독성이 떨어지는 것 같다.
집중국은 수신영역을 0에서부터 무한대까지 늘릴 수 있다.
만약 집중국과 센서가 1대1이라면 수신영역은 0이 될 것이다. 만약 센서가 좌표 3과 4에 있을 때 하나의 집중국이 이를 전부 커버친다면 수신영역은 1이 될 것이다.

즉 '센서와 센서 사이 구간이 긴 부분' 은 하나의 집중국이 전체 커버치지 않도록 스마트하게 갈라서 최소 수신 영역을 내라는 문제이다.

문제처럼 위와 같이 주어졌을 때, 제일 먼 구간은 3에서 6으로 가는 구간이다. 마침 집중국이 2개가 주어졌으므로 이를 기준으로 좌우로 나누면 된다.

만약 집중국이 3개 주어졌다면, 2번째로 긴 구간인 7~9 혹은 1~3 또한 두 개의 집중국으로 나눠주면 되겠다.

2. 코드가 나오기까지 🛠️

KEY WORD: 그리디 알고리즘

제일 긴 구간을 될 수 있는 한, 지워나간다는 점에서 그리디 알고리즘 이라고 볼 수 있겠다. 그럼 얼마나 지울 수 있는가?

(1) 구간을 지울 수 있는 양

집중국이 2개면 전체 구간을 두 덩어리로 나눌 수 있다는 뜻이다. 즉 원래 존재하던 모든 구간 중 하나를 지워 2 분할한다. (집중국 2개 = 지우는 구간 1개)

집중국이 3개면 전체를 세 덩어리로 나눠야 하므로 기존재하던 구간 중 2개를 지워 분할해야 한다.
(집중국 3개 = 지우는 구간 2개)

이렇게 생각하면, 집중국 K개에 지울 수 있는 구간은 K-1 개 가 나옴을 알 수 있다.

(2) 시간복잡도 분석 ⏳

N개의 입력을 받아 각 구간을 구하고 그 중 K개를 지우면 된다. 모든 과정이 불연속적인 1차원 배열 순회임으로 시간복잡도는 O(N) 이다.

3. 코드 🌐

(1) SUDO CODE 💬


// 간단한 의사 코드 생략

(2) JAVA CODE ☕


import java.util.*;
import java.io.*;
 // b 17255 N으로 만들기
public class Main {
    static int N,K;
    static int [] arr;
    static int [] interval;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        K = Integer.parseInt(br.readLine());
        arr = new int [N];
        interval = new int [N-1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }        Arrays.sort(arr);
        for(int i = 0; i < N-1; i++){
            interval[i] = arr[i+1] - arr[i];
        }        Arrays.sort(interval);

        int delete = K-1;
        for(int i = N-2; i >= 0; i--){
            if(delete == 0) break;
            interval[i] = 0;
            delete--;
        }

        int answer = 0;
        for(int i = 0; i < N-1; i++){
            answer += interval[i];
        }        System.out.println(answer);
    } }