[BOJ] 1449 수리공 항승

수리공 항승

풀이

• 길이가 L인 테이프가 무한개, 테이프로 물을 막을 때, 적어도 그 위치의 0.5만큼 간격을 줘야한다.
• 항승이가 필요한 테이프의 최소 개수를 구해라.
• 만약에 물이 새는 곳 위치가 1 2 100 101, L=2 이렇게 주어지면, 1에서 부터 테이프를 붙여서 1-0.5~ 2+0.5) 범위를 감싸면 조건을 충족시킨게 된다.
• 그래서 일단 주어지는 물새는 곳 위치 배열을 오름차순 정렬한 다음, for문으로 배열을 순회하면서 최댓값 arr[i]+L-0.5 범위 내에 들어오는지 확인하고, 안 들어오면 cnt++ 늘려주고 max값 갱신하여 필요한 테이프 개수를 센다.

정답 풀이

import java.util.*;
import java.io.*;
public class BOJ1449 {
    public static void main(String[] args) throws Exception{
        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[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        int cnt = 0;
        double max = -1;
        for(int i=0;i<arr.length;i++) {
            if (arr[i] <= max) continue;
            max = arr[i] + L - 0.5;
            cnt++;
        }
        System.out.println(cnt);
    }
}