백준 1911번: 흙길 보수하기

문제 설명

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

접근법

• 입력이 뒤죽박죽으로 들어오기 때문에 정렬이 필요합니다.
• 입력정보에서 끝 위치는 덮지 않아도 됩니다.
  • 웅덩이의 정보가 1 6이 들어온다면 1번,2번,3번,4번,5번을 덮으면 된다는 의미입니다.
• 물웅덩이의 시작지점부터 널빤지를 댑니다. (그리디한 접근)
• 이전 널빤지로 인해 시작지점이 달라질 수 있습니다.
  • 다음 시작지점 = Math.max(입력으로 주어진 시작지점, 이전 널빤지가 끝난 다음위치)

정답

import java.util.*;
import java.io.*;

public class Main {
	static int totalCnt = 0;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int L = sc.nextInt();
		List<int[]> lst = new LinkedList<int[]>();
		for (int i = 0; i < N; i++) {
			int from = sc.nextInt();
			int to = sc.nextInt()-1;
			lst.add(new int[] {from,to});			
		}		
		Collections.sort(lst,new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0];
			}			
		});
		int now = 0;
		for (int i = 0; i < N; i++) {
			int[] temp = lst.get(i);
			if(temp[1]<now) continue; // 이미 이전 널빤지로 웅덩이 전체가 덮혔다면 continue
			int start = Math.max(now, temp[0]);
			now = func(start,temp[1],L);
		}
		System.out.println(totalCnt);
	}
	
    // 널빤지를 대고난 후의 다음 시작지점을 반환
	public static int func(int from, int to, int L) {
		int x = (to+1 - from)/L;
		if((to+1-from)%L != 0) {
			x++;
		}
		totalCnt +=x;
		return from + x*L;

	}
	
}