[백준] 1449 : 수리공 항승 - Java

• 백준 문제 URL

---

문제 요약

n개의 물이 새는 위치(구멍 좌표)가 주어질 때, 길이가 l인 테이프로 모든 구멍을 막기 위해 필요한 테이프 개수의 최솟값을 출력하는 문제다.
테이프는 구멍을 중심으로 일정 구간을 덮을 수 있고, 구멍 위치들이 주어졌을 때 “최소 몇 개를 붙이면 전부 커버되는지”를 묻는다.

---

핵심 아이디어

이 문제는 “가장 왼쪽(가장 작은 위치)의 아직 안 막은 구멍”부터 테이프를 붙이는 선택이 항상 이득이라서 Greedy로 풀 수 있다.
한 번 테이프를 붙이면 그 테이프가 덮는 범위 안에 들어오는 구멍들은 어차피 같은 테이프로 처리하는 게 최적이므로, 가능한 만큼 최대한 덮고 다음으로 넘어가는 방식이 된다.

---

풀이 흐름(정렬 + 커버 범위 스킵)

1) 정렬이 먼저 필요한 이유

구멍 위치를 정렬해두면 “왼쪽부터 차례대로 막기”가 가능해진다.
정렬이 되어 있어야 현재 테이프가 덮는 범위를 기준으로 “다음 구멍이 커버 안이면 스킵”을 안정적으로 할 수 있다.

2) 테이프 1개를 붙였을 때 커버 범위

현재 구멍을 startSpot으로 잡으면, (정수 기준으로) 테이프가 덮는 마지막 지점을

• coverEnd = startSpot + l - 1

로 계산할 수 있다.

3) 스캔(1-pass) 방식

• 아직 처리하지 않은 가장 왼쪽 구멍에 테이프를 붙인다. (count++)
• 그 테이프로 덮을 수 있는 범위(coverEnd) 안에 들어오는 구멍은 전부 스킵한다.
• 커버 범위를 벗어나는 다음 구멍을 만나면 다시 테이프를 붙인다.
• 인덱스 i가 n에 도달하면 종료한다.

---

전체 코드(제출용)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken()); // 구멍 수
        int l = Integer.parseInt(st.nextToken()); // 테이프 길이

        int[] spotArr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            spotArr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(spotArr);

        int count = 0;
        int i = 0;

        // 구멍 위치를 정렬해두고, 왼쪽(가장 작은 위치)부터 순서대로 처리한다.
        // 현재 구멍을 테이프 시작점(startSpot)으로 잡고,
        // 그 테이프로 덮을 수 있는 범위(coverEnd) 안에 들어오는 다음 구멍들은 계속 넘어간다(스킵).
        // 다음 구멍이 coverEnd를 넘는 순간, 새 테이프가 필요하므로 count를 1 증가시키고
        // 그 구멍을 새로운 startSpot으로 갱신해서 같은 과정을 반복한다.
        // 모든 구멍을 처리(i가 끝까지 감)하면 종료한다.
        while (i < n) {
            int startSpot = spotArr[i];
            int coverEnd = startSpot + l - 1;

            count++;
            i++;

            while (i < n && spotArr[i] <= coverEnd) {
                i++;
            }
        }

        System.out.println(count);
    }
}