백준 1449번 : 수리공 항승

 문제

www.acmicpc.net/problem/1449

1449번: 수리공 항승

1449 수리공 항승

 

 구현 방법

테이프 하나로 물이 새는 곳을 막을 때 테이프만큼의 길이 내에 있으면 같이 물을 막을 수 있습니다.

수를 정렬한 후 제일 작은 값부터 시작하여 테이프로 막아줍니다. 테이프 길이 내에 있으면 그냥 막아지고 길이를 벗어나면 새로운 테이프로 막아줍니다.

 

예제를 통해 예를 들어보겠습니다.

물이 새는 곳의 위치들이 1 2 100 101, 테이프 길이가 2 일 때 테이프는 제일 작은 값인 1부터 막기 시작합니다.

0.5만큼 간격을 줘야하기 때문에 처음 테이프는 0.5 - 2.5만큼이 막아지므로 다음 위치인 2도 막아집니다.

다음 위치인 100은 마지막 테이프 위치인 2.5를 벗어났기 때문에 새로운 테이프로 막아줘야 합니다. 

이런식으로 모든 위치를 탐색하면 끝입니다.

 

 구현 코드

package BOJ.Silver;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class B1449_수리공항승 {
	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());
		int[] water = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i=0;i<N;i++) {
			water[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(water);
		int fixF = 0, fixL = 0, cnt = 0;
		for (int i=0;i<N;i++) {
			if (fixF>=water[i] || water[i]>=fixL) { // 위치가 테이프 길이를 벗어날 때
				cnt++;
				fixF = water[i];
				fixL = water[i]+L;  
			}
		}
		System.out.println(cnt);
	}
}

 

정답!