[백준/JAVA] 1911번: 흙길 보수하기

🔺 문제

1911번: 흙길 보수하기

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.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(br.readLine(), " ");
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
 
        // [1. 웅덩이 정렬]
        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]);
           }
        });
        
        // [2. 웅덩이 순회하며 널빤지 깜]
        int cnt = 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;
                    cnt++;
                }
            }
        }
        
        System.out.println(cnt);
    }
}

✅ 해결 아이디어
✔ 정렬 & 그리디
1] 웅덩이 정렬 (Line 22-28)
  - 물 웅덩이 시작 위치 기준으로 오름차순 정렬
  - 시작 위치가 동일한 경우, 끝 위치 기준으로 오름차순 정렬
2] 웅덩이 순회하며 널지찌 깔기 (Line 30-43)
 - 만약 웅덩이 시작 위치 > range라면, 새로 널빤지를 덮어야 하므로 시작 위치를 range로 설정
 - 만약 웅덩이 끝     위치 > range라면, 널빤지를 깔고 range를 널빤지 길이만큼 증가시킴
 - while문이 돌 때마다 널빤지 개수인 answer + 1

 

---

🔺 다른 풀이들

- 다들 비슷하심

 

---

💬 느낀 점

후엥 그리디 쉽지 않구나.....ㅠ

복습을 245만번해야할듯..

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔

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

[백준] Java 1911 흙길 보수하기