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

 

 

 

문제 출저

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

1911번: 흙길 보수하기

 

 

 

문제 풀이

웅덩이 n개, 판자의 길이 l 이 주어집니다.

웅덩의 시작과 끝이 주어질 때 몇 개의 판자로 웅덩이를 모두 막을 수 있는지 구해야 합니다. 

 

정렬과 구현으로 문제를 풀었습니다.

웅덩의 시작 지점, 끝 지점으로 오름차순으로 이중 정렬을 했습니다.

그 다음은 int range 변수를 설정해서 판자를 표시했습니다. 

시작지점부터 시작해서 while 문으로 계속 판자를 붙여서 웅덩이 끝 지점이면 while 문을 멈췄습니다. 

이를 통해 답을 구했습니다.

 

 

소스 코드 

package baekjoon.backjoon10.day2131.day24;


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/*
흙길 보수하기
https://www.acmicpc.net/problem/1911
 */
public class B1911 {

    static int n;
    static int l;
    static List<WaterHole> waterHoleList;

    static int range;
    static int answer;


    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());
        waterHoleList = new ArrayList<>();

        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            waterHoleList.add(new WaterHole(start, end));
        }

        Collections.sort(waterHoleList);

        range = 0;
        answer = 0;

        for(WaterHole data : waterHoleList) {

            if(data.start > range) {
                range = data.start;
            }

            while(true) {
                if(data.end > range) {
                    range += l;
                    answer++;
                }
                else {
                    break;
                }
            }

        }

        System.out.println(answer);

    }


    public static class WaterHole implements Comparable<WaterHole> {
        int start;
        int end;

        WaterHole(int start, int end) {
            this.start = start;
            this.end = end;
        }

        public int compareTo(WaterHole w) {
            if(this.start == w.start) {
                return this.end - w.end;
            }
            return this.start - w.start;
        }

    }

}