1911번 흙길 보수하기

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

# 복습

# 코딩

# 코테

# 문제

# 그리디(Greedy)

처음에는 

6 - 1 = 5

17 - 13 = 4

12 - 8 = 4

합은 13이고 13/3 = 4.** = 4,

나머지가 있으므로 5

이렇게 생각했는데 그게 아니었다.

(반례)

2 2

1 2

3 4

2

주석을 참고.

핵심 : 널빤지를 어느 (시작) 위치에 설치를 할 것인가? 물웅덩이의 시작 좌표와 함께 고려하기

단순하면서도 생각을 조금 요구하는 문제.

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int N;
    static long ans = 0, L;
    static Vector<Pair> v = new Vector<Pair>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        L = Long.parseLong(st.nextToken());
        
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());            
            long f = Long.parseLong(st.nextToken());
            long s = Long.parseLong(st.nextToken());
            v.add(new Pair(f, s));
        }
        
        Collections.sort(v, new Comparator<Pair>() {
            public int compare(Pair a, Pair b) {
                return Long.compare(a.first, b.first);
            }
        });
        
        long here = 0; // 널빤지의 끝 위치(오른쪽)
        
        for(int i = 0; i<v.size(); i++) {
            
            long len1 = v.get(i).second - v.get(i).first; // here이 v.get(i).first보다 작거나 같을 때
            long len2 = v.get(i).second - here; // here이 v.get(i).first보다 클 때
            long cnt = 0;
            
            // 0이 나오면 진행할 필요가 없음.(덮으므로)
            if(len1 <= 0 || len2 <= 0) continue;
                    
            if(here <= v.get(i).first) {
                // 현재 널빤지의 오른쪽 끝이 현재 물웅덩이 시작점보다 작거나 같다면
                here = v.get(i).first; // here의 위치를 옮긴다. 
                cnt = len1/L; // 널빤지 개수 구하기(원래의 물웅덩이 길이를 고려)
                if(len1 % L != 0) ++cnt; // 나머지가 있다면 널빤지 1개 추가)
            }
            else {
                // 현재 널빤지의 오른쪽 끝이 현재 물웅덩이 시작점보다 크다면
                cnt = len2/L; // 널빤지 개수 구하기(물웅덩이의 시작  부분의 일부를 덮은 here를 고려)
                if(len2 % L != 0) ++cnt; // 나머지가 있다면 널빤지 1개 추가)
            }        
            
            here += cnt * L; // 설치한 널빤지의 총 길이를 here에 더함
            ans += cnt;
        }
            
        bw.write(String.valueOf(ans) + "\n");
        bw.flush();
        bw.close();
    }
}
 
class Pair{
    long first, second;
    Pair(long f, long s) {
        this.first = f;
        this.second = s;
    }
}