[PS] BOJ1911 흙길 보수하기 ( Line Sweeping ) with JAVA

 

1911번: 흙길 보수하기

 

 

◎ 문제풀이

 

 

 

 

풀이를 알면 굉장히 쉬운 문제인데...

쉬운 풀이까지 가기란 참으로 어려운 것 같다. 

 

변수(range)를 하나 선언한다.

변수(range)는 현재 설치된 널빤지 정보를 갖는다. 

 

range가 9이면

현재 9까지 널빤지가 설치된 것이다. 

 

처음에는 설치된 널빤지가 없으니

range는 0이다.

 

다음 물웅덩이가 3(start)부터 10(end)까지라고 가정해보자.

 

start(3)가 range(0)보다 크므로 range를 start(3)로 갱신한다. 

end(10)가 range(3)보다 크므로 널빤지 길이(l)만큼 range를 더해간다. (while문)

이때 더한 횟수가 널빤지의 개수가 된다. 

 

널빤지 길이(l)가 3이라면 

 

널빤지 1 : 3-5 ( range = 5 )

널빤지 2 : 6-8 ( range = 8 )

널빤지 3 : 9-11 ( range = 11 )

 

range는 11이고 웅덩이는 10까지 이므로 반복을 종료한다.

현재까지 웅덩이를 덮는데 사용된 널빤지의 개수는 총 3개이다. 

 

 

다음 물웅덩이가 11(start)부터 15(end)까지라고 해보자. 

 

range는 11이다. start가 range보다 크지 않으니 갱신하지 않는다. 

end는 range보다 크므로 널빤지 길이만큼 range를 더해간다. 

 

널빤지 4: 11-13

널빤지 5 : 14-16

 

range는 16이고 웅덩이는 15까지이니 반복을 종료한다. 

현재까지 웅덩이를 덮는데 사용된 널빤지의 개수는 총 5개이다.

 

이와 같은 원리로 모든 웅덩이를 반복하면 된다. 웅덩이는 시작점을 기준으로 오름차순 정렬하고 시작점이 같다면 끝점을 기준으로 오름차순 정렬한다. 

 

 

◎ 코드

package org.example.greedy;


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


//BOJ1911 흙길 보수하기
public class Greedy18 {


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

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

        @Override
        public int compareTo(Pool p) {
            if(this.start == p.start) return this.end - p.end; 
            return this.start - p.start;
        }
    }
    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());

        Pool[] pools = new Pool[n];

        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            pools[i] = new Pool(start,end);
        }

        // 물웅덩이 정렬
        Arrays.sort(pools);

        int ans = 0;
        int range = 0;
        
        for (Pool pool : pools) {
            // start와 range 비교
            if(pool.start > range){
                range = pool.start; //range 갱신
            }

            // end오 range 비교
            if(pool.end > range){
                while( pool.end > range ){
                    range += l; // range 갱신 
                    ans+=1; // 널빤지 갱신
                }
            }
        }

        System.out.println(ans);
    }

}