[BOJ] 1449 수리공 항승 (Java)

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

 

 

그리디는 항상 해결방법을 떠올리는 게 참 어려운 것 같다,,

이 문제는 주어진 물이 새는 곳의 위치를 정렬 해 두고, 주어진 테이프 길이 안에 위치하는 지 확인하면 되는 문제이다.

즉, 첫번째 위치에서 -0 .5를 시작지점(left)로 두고 + 테이프의 길이(l) 안에 다음 물이 새는 위치가 더 오른쪽에 위치한다면

테이프의 개수를 1 카운트하고, 시작지점을 다음 물이 새는 위치 - 0.5 지점으로 변경해주면 된다.

 

 

<제출코드>

package BOJ.Greedy;

import java.util.Arrays;
import java.util.Scanner;

public class BOJ_1449_수리공항승 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int l = sc.nextInt();

        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);

        double left = arr[0] - 0.5;
        int cnt = 01;
        for(int i=0; i<n; i++){
            double right = left + l;
            if(arr[i] > right) {
                cnt++;
                left = arr[i] - 0.5;
            }
        }
        System.out.println(cnt);
    }
}