링크

백준 - 흙길보수하기

문제

어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N (1 <= N <= 10,000) 개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이 L (L은 양의 정수) 짜리 널빤지들을 충분히 가지고 있어서, 이들로 다리를 만들어 물웅덩이들을 모두 덮으려고 한다. 물웅덩이들의 위치와 크기에 대한 정보가 주어질 때, 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 구하여라.

입력

첫째 줄에 N과 L이 들어온다.

둘째 줄부터 N+1번째 줄까지 총 N개의 줄에 각각의 웅덩이들의 정보가 주어진다. 웅덩이의 정보는 웅덩이의 시작 위치와 끝 위치로 이루어진다. 각 위치는 0이상 1,000,000,000이하의 정수이다.

출력

첫째 줄에 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 출력한다.

풀이

우선 입력값의 시작값을 오름차순으로 만든다.

		Collections.sort(list, new Comparator<int[]>() {
			public int compare(int[] o1, int[] o2)
			{
				if(o1[0] > o1[0])
					return o1[0]-o2[0];
				else
					return o1[1]-o2[1];
			}
		});

다음, 배열에는 물 웅덩이의 시작위치를 기준으로 정렬이 되어있으므로, 앞에서부터 비교해가며 필요한 널빤지의 개수를 구하면 되는데, range 변수는 널빤지로 물웅덩이를 덮었을때, 어디까지 덮을 수 있는지 나타내는 범위이다.

만약 물 웅덩이의 시작 위치가 range 범위보다 크다면, 이 곳은 널빤지를 덮어야 하므로 웅덩이의 시작 위치를 range 범위로 설정한다.
만약 range가 더 크다면 바꿀 필요가 없다.
왜? -> 다음 시작하는 위치보다 널빤지를 더 뒤덮었기 때문에 range부터 시작하면 되기 때문이다.

그 후 웅덩이의 끝나는 위치까지 널빤지를 덮어야 하는데,
웅덩이의 끝나는 위치(y) 가 범위(range)보다 클 때 까지 널빤지를 덮고, 범위를 널빤지 길이만큼 늘린다

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class practice {	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		ArrayList<int[]> list=new ArrayList<int[]>();
		
		int n=Integer.parseInt(st.nextToken());
		int l=Integer.parseInt(st.nextToken());
		int count=0;
		
		for(int i=0; i<n; i++)
		{
			StringTokenizer st1=new StringTokenizer(br.readLine());
			int start=Integer.parseInt(st1.nextToken());
			int end=Integer.parseInt(st1.nextToken());
			list.add(new int[] {start, end-1});
		}
		
		Collections.sort(list, new Comparator<int[]>() {
			public int compare(int[] o1, int[] o2)
			{
				if(o1[0] > o1[0])
					return o1[0]-o2[0];
				else
					return o1[1]-o2[1];
			}
		});
		
		int range=0;
		
		for(int i=0; i<n; i++)
		{
			int arr[]=list.get(i);
			int x=arr[0];
			int y=arr[1];
			
			if(x>range) //range를 시작위치로 설정
				range=x;
			
			while(y>=range)
			{
				range+=l;
				count++;
			}
		}
		
		System.out.println(count);
	}
}