[BOJ] 백준 1449 수리공 항승

출처: https://www.acmicpc.net/problem/1449

 Input 

4 2

1 2 100 101

 

 Output 

2　

* 문제에서는 좌우 간격을 0.5를 주어야 한다고 하였으며,

다시말해, 테이프로 해당 좌표를 덮어씌울 수 있으면 됩니다.

 

물이 새는 곳의 위치는 다음과 같으면 L = 2이기 때문에 2개의 테이프만 있으면 됩니다.

왼쪽에서부터 테이프를 차례대로 겹치지 않게 붙입니다.

 

구현

① 새어나오는 곳의 위치를 오름차순 정렬

    (※ 실제 Input Data에서 Random하게 주어짐)

②  테이프 길이 L을 최대한 활용하며 테이프를 붙입니다.

      + 적은 테이프로 많은 곳에 붙여야 합니다.

 

새어나오는 위치 두 『1』, 『3』 를 테이프 1개로 붙이고 『100』에 1개 더 붙여 총 2개가 필요.

 Input 

3 3

1 3 100

 

 Output 

2 

 

테이프의 길이가 3(=L)이기 때문에 새어나오는 곳마다 테이프 1개씩 필요

 Input 

3 3

1 4 100

 

 Output 

3

---

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new  Scanner(System.in);
         
        // 1 <= N, L <= 1,000
        int N = Integer.parseInt(sc.next());
        int L = Integer.parseInt(sc.next());
         
        List<Integer> hole = new ArrayList<>();
         
        // 구멍 입력 받기
        while(N-- > 0) {
            hole.add(Integer.parseInt(sc.next()));
        }
         
        // 위치를 오름차순으로 정렬
        Collections.sort(hole);
         
        int answer = 1;
         
        // 한 개의 구멍은 들어 있으므로 우선 출발점으로 설정
        int A = hole.remove(0);
 
 
        // 테이프 개수를 최소화하면서 모든 구멍을 메운다.
        while(!hole.isEmpty()) {
            int B = hole.remove(0);
             
            // 지금 tape는 cover가능한 최대 구멍개수(범위)를 알아낸다.
            if(B-A <= L-1) continue;
             
            A = B; // 새로운 출발점으로 설정해서 계속 탐색
            answer++;
             
        }
         
        System.out.println(answer);
    }
}