백준 흙길 보수하기 1911 자바

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

 

 

 

음... 그냥 단순하게 정렬한 후 널빤지의 개수를 구하면 된다.

주의해야 할 건 널빤지의 길이는 정해져 있기 때문에 물웅덩이가 아닌 위치도 널빤지로 덮을 수 있다는 점.

 

만약 물웅덩이의 위치가 [1,5] [10,15] 이고, 널빤지의 길이가 20이라면 널빤지의 모든 물웅덩이를 커버 가능하다.

 

이부분만 생각해서 풀면 되는 간단한(?) 문제였다. 딱히 정렬말고 알고리즘을 쓸 필요도 없음...

 

 

물웅덩이는 최대 만개이다.

 

웅덩이의 위치값은 최소 0에서 최대 10억이다.

 

시간복잡도를 고려하면 범위를 for문으로 돌리면 안된다는 걸 알 수 있다.

 

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

public class Main {

    public static int answer = 0;
    public static int N,L;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
		
        // 물웅덩이 위치 저장
        int[] waters = new int[2*N];

        for (int i=0; i<2*N; i+=2) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            waters[i] = start;
            waters[i+1] = end;
        }
		
        // 정렬해도 상관 없다. 입력에서 물웅덩이 위치가 겹치는 범위는 없으므로
        Arrays.sort(waters);
		
        // 널빤지의 가장 마지막 위치를 기억한다.
        int lastIdx = 0;

        for (int i=0; i<2*N; i+=2) {

            int start = waters[i];
            
            이미 물웅덩이에 널빤지가 존재한다면,
            시작점을 널빤지의 가장 마지막 위치 + 1로 잡는다.
            if (lastIdx >= start) {
                start = lastIdx + 1;
            }
            int end = waters[i+1];
            int length = end - start;
            
            // 이미 널빤지가 대져있을 수도 있기 때문에, 이런 경우는 continue
            if (length <= 0) continue;

		
       		// 널빤지 개수
            int cnt = length/L;

			// 널빤지 대고 남는 부분
            int res = length%L;

			// 남는 부분이 있으면, 널빤지개수를 1 증가시키고 마지막 널빤지위치를 구한다.
            if (res != 0) {
                cnt++;
                lastIdx = waters[i+1]-1 + (L - res);
            }

			// 답에 카운트 더하기
            answer += cnt;
        }

        System.out.println(answer);
    }
}