[백준] 1911번: 흙길 보수하기(그리디)

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

1911번: 흙길 보수하기

코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int N = Integer.parseInt(st.nextToken());	// 웅덩이 개수
		int L = Integer.parseInt(st.nextToken());	// 널빤지 길이
		int[][] arr = new int[N][2];	// 물 웅덩이 시작, 끝위치
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(bf.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arr, new Comparator<int []>() {

			// 물웅덩이의 시작 위치를 기준으로 오름차순 -> 시작 위치가 동일하면 끝 위치를 기준으로 오름차순
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[0] == o2[0])
					return Integer.compare(o1[1], o2[1]);
				return Integer.compare(o1[0], o2[0]);
			}
		});
		
		int nulpan = 0;	// 필요한 널빤지의 개수
		int range = 0;	// 널빤지를 물웅덮이에 덮었을때, 덮을 수 있는 범위
		for(int i=0; i<N; i++) {
			if(arr[i][0] > range)
				range = arr[i][0];
			if(arr[i][1] >= range) {
				while(arr[i][1] > range) {
					range += L;
					nulpan ++;
				}
			}
		}

		System.out.println(nulpan);
		bf.close();
	}

}

풀이

일단 그리디 문제여서 하나하나 탐욕스럽게 접근할거기 때문에, 주어진 물 웅덩이의 시작위치, 끝위치를 정렬을 해야겠다는 생각을 했다. 정렬 조건은 물 웅덩이의 시작 위치가 가장 작은 것 부터, 같으면 끝위치가 작은것부터 정렬했다.

 

Comparator 인터페이스 참고

 

그 후, 하나하나 비교해가며 널빤지를 설치할 것인지? 설치한다면 몇개설치하는지 판단을 하면 되는데 여기서 너무 생각이 많아지고 헷갈렸다.

 

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

 

만약 물 웅덩이의 시작 위치가 range 범위보다 크다면, 이 곳은 널빤지를 덮어야 하므로 웅덩이의 시작 위치를 range 범위로 설정한다. 

그 후 웅덩이의 끝나는 위치까지 널빤지를 덮어야 하는데,

웅덩이의 끝나는 위치(arr[i][1]) 가 범위(range)보다 클 때 까지 널빤지를 덮고, 범위를 널빤지 길이만큼 늘린다

				while(arr[i][1] > range) {
					range += L;
					nulpan ++;
				}

 

위 풀이를 요약하면 다음과 같다.

● 현재 물웅덩이의 시작 위치와 이전에 설치한 널빤지의 범위를 비교한다.

● 만약 현재 물 웅덩이의 시작 위치가 이전 설치한 널빤지의 범위보다 크면 널빤지를 덮어야한다.

● 새로 널빤지를 덮어야 하는 부분이므로, 범위를 물 웅덩이의 시작 위치로 지정한다. range = arr[i][0]

● 물 웅덩이의 끝나는 위치가 널빤지 범위보다 큰경우 - 물 웅덩이의 끝나는 위치까지 널빤지를 계속 덮는다.

 

 

그리디 문제 너무 머리아프다...

비슷한 문제는 다음과 같다.

 

백준 1449번 수리공항승

프로그래머스 기지국설치