(JAVA) 백준 1911번, 흙길 보수하기

 

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

1911번: 흙길 보수하기

문제 난이도 : Silver1

 

#알고리즘 분류 : 그리디,정렬,스와이프

 

#문제

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

 

#입력

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

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

 

#출력

널빤지의 갯수

 

#풀이방법

2차원 배열로 입력받아

웅덩이의 시작 순서대로 오름차순으로 정렬한다. 이때 시작이 같으면 끝이 낮은 것이 우선된다.

 

range라는 변수를 따로 만들어 range를 널빤지의 끝에 계속 업데이트 시켜서

이전 웅덩이에 널빤지와 겹치는 부분이 있다면  비교하여 초기값을 range라 할 것인지 웅덩이의 시작부분으로 할 것인지 반복문을 사용해 널빤지 개수를 플러스 시킨다.

 

 

 

#전체코드

import java.util.*;
//2t

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();// 웅덩이 갯수
		int[][] pow = new int[N][2];
		
		int min = Integer.MAX_VALUE;
		int max = 0;
		
		int L = sc.nextInt(); // 덮을 수 있는 길이
		
		for(int i=0; i<pow.length; i++) {
			
			pow[i][0] = sc.nextInt();
			pow[i][1] = sc.nextInt();
			
			if(min < pow[i][0])
				min = pow[i][0];
			
			if(max < pow[i][1])
				max = pow[i][1];
		}
		
		Arrays.sort(pow,(o1,o2)->{
			
			if(o1[0] == o2[0]) {
				return Integer.compare(o1[1], o2[1]);
			}
			else {
				return Integer.compare(o1[0],o2[0]);
			}
			
		});//시작순서대로 정렬하기
		
		
		int num = 0;//널빤지의 갯수
		int j;
		int range = 0;
		
		for(int i=0; i<pow.length; i++) {
			
			if(range > pow[i][0]) {
				j = range;
			}
			else
				j = pow[i][0];
			
			for(;j<pow[i][1];) {
				j+=L;
				range = j;
				num++;
			}
			
		}
		
		System.out.println(num);
		
		
	}

}