백준 No.1449 수리공 항승 - JAVA

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

1449번: 수리공 항승

문제

항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다.

파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 센다.

항승이는 길이가 L인 테이프를 무한개 가지고 있다.

항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다. 물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다.

 

입력
첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물인 새는 곳의 위치는 1, 000보다 작거나 같은 자연수이다.

4 2
1 2 100 101

 

처음부터 L만큼 근처에 다음 구멍이 있다면 테이프를 안 써도 되는 식으로 구현했는데 3,2,1 같이 붙어있는 값을 해결하지 못함 - > 문제에서 0.5가 힌트였음

풀이

- 오름차순으로 정렬하고 맨 좌측 구멍 왼쪽으로 0.5 거리만큼을 구하고 거기부터 테이프를 붙이기 때문에 +L(테이프길이).  -->> (arr[0] -0.5+L)   처음 붙힌 테이프이다.

- 이제 다음 값들이 만약 자신들의 우측으로 0.5 까지 해당 테이프가 덮지 못한다면 자신들의 테이프를 붙혀야한다. 그러고 자신들의 테이프를 붙혔으니 값도 변경되어야 한다. 이제 자신들의 테이프를 쭉 이어나간다. (자신의 우측 0.5 --> arr[i]+0.5)

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 M = Integer.parseInt(st.nextToken());   //배열크기
        int L = Integer.parseInt(st.nextToken());

        int arr[] = new int[M];
        st = new StringTokenizer(br.readLine());
        for(int i= 0;i<M;i++){
                arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);   
        int range = (int)(arr[0]- 0.5 + L); //최소 0.5이므로 0.5전부터 테이브 길이 이 값을 다음 값이 벗어난다면 하나 붙이는 식으로
        int count = 1;  //가장 첫번째는 담았기에 카운트
    //다음거랑 L범위 안에 있다면 카운트 1 아니면 2
     
        for(int i=1;i<arr.length;i++){
            if(range <(int)(arr[i]+0.5)){
                range = (int)(arr[i]-0.5 + L);
                count++;
            }
        }

        System.out.println(count);
    }
}