[자바] 백준 1449번: 수리공 항승

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

1449번: 수리공 항승

---

테이프 하나로 붙일 수 있는 곳은 한번에 다 붙인다

라는 생각으로 풀었다

 

우선 구멍난 곳의 위치를 오름차순으로 정렬 해 둔다(그럼 앞에 있는 구멍부터 볼 수 있다)

앞에있는 구멍부터 테이프를 하나씩 뜯어서 구멍을 막을건데

뜯은 테이프로 같이 막을 수 있는 구멍은 같이 막자.

테이프의 시작위치는 구멍-0.5, 테이프의 끝나는 위치는 구멍-0.5+L이다.

 

테이프의 끝나는 위치보다 안에 있는 구멍은 굳이 새 테이프를 사용하지 않아도 같이 메꿀 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class P1449 {

	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());

		LinkedList<Integer> broken = new LinkedList<>();

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

		Collections.sort(broken);

		int count = 0;
		while (!broken.isEmpty()) {
			count++;
			double tape_length = broken.pop() - 0.5 + l;
			while (!broken.isEmpty() && broken.peek() <= tape_length) {
				broken.pop();
			}
		}

		System.out.println(count);
	}

}