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

풀이 아이디어

그리디

• int covers: 커버에 사용한 널판지 수
• coversIndex: 커버할 널판지 인덱스(해당 인덱스는 아직 덮지 않은 부분)
• Water: 웅덩이의 시작좌표(Water.start), 끝좌표(Water.end)를 저장하는 객체
• remain: n개의 널판지로 덮을 때 웅덩이 끝좌표를 넘는 길이
  예) l=3이고 웅덩이가1 5이면 1~4커버를 해야하는데 4=3*1+1로 remain==1이 된다.

웅덩이 시작과 끝 위치를 n개의 널판지로 딱 맞게 덮는 경우와
남게 더 덮는 경우를 나눠서 널판지 개수와 가리키는 인덱스 coversIndex를 조정한다.
이때 널판지 개수가 얼마나 필요한지는 (water.end - coversIndex)/l 로 구했고
다음 덮은 포인터를 가리킬 좌표를 (water.end - coversIndex)%l로 구했다.

트러블 슈팅

문제 설명과 다른 웅덩이 범위

문제의 설명과 예제가 맞지 않는 부분이 있어서 애를 먹었다.
예제 케이스에서 입출력이 아래처럼 주어진다면

// 입력
3 3
1 6
13 17
8 12
// 출력
5

힌트는 이렇게 표시가 되는데

111222..333444555.... // 길이 3인 널빤지
.MMMMM..MMMM.MMMM.... // 웅덩이
012345678901234567890 // 좌표

예제를 잘 보면 웅덩이가 끝 좌표는 웅덩이에 해당하지 않아서
1 6 웅덩이면 1~5까지만 실제로 커버해야하는 범위다.

이미 새로 커버한 경우 예외처리

논리가 맞는 것 같았는데 자꾸 4%에서 틀렸었다.
어디가 잘못되었는지 봤는데
질문 게시판의 예외 케이스를 보니 알 수 있었는데

// 입력
3 10
1 6
7 8
11 15

// 출력
2

아래 케이스에서 3이 나왔었다.
알고보니 coversIndex > water.end로 다음 웅덩이까지 이미 덮은 경우
covers를 증가시키지 않고 다음 웅덩이로 넘어가야하는데
예외처리를 안해서 한 번더 covers를 계산되어 오류가 발생했다.
그래서 아래처럼 예외처리를 해줬다.

if(coversIndex > water.end){
	continue;
} 

풀이 코드

import java.util.*;
import java.io.*;
public class _1911 {
    // 물 웅덩이를 받을 객체
    static class Water{
        int start;
        int end;
        Water(int start, int end){
            this.start = start;
            this.end = end;
        }
    }
    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()); // n: 웅덩이 수
        int l = Integer.parseInt(st.nextToken()); // l: 널판지 길이

        int lastWater = 0; // 물 웅덩이 중 가장 먼 좌표
        ArrayList<Water> waterInputList = 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()); // 웅덩이 끝 좌표
            // 가장 멀리있는 웅덩이 좌표 구하기
            if(end>lastWater){
                lastWater=end;
            }
            waterInputList.add(new Water(start, end)); // 리스트에 웅덩이 정보 저장
        }

        // 시작 좌표 -> 끝 좌표 순서로 오름차순으로 정렬
        Collections.sort(waterInputList, new Comparator<Water>(){
            @Override
            public int compare(Water o1, Water o2) {
                if(o1.start==o2.start)
                    return o1.end-o2.end;
                else
                    return o1.start-o2.start;
            }
        });
        
        int covers = 0; // 커버된 널판지 수
        int coversIndex = -1; // 커버된 널판지 인덱스
        
        // 입력된 모든 웅덩이를 기준으로 정렬
        for(Water water : waterInputList){
            // 이미 웅덩이가 덮인 경우 다음 웅덩이로 넘어간다
            if(coversIndex > water.end){
                continue;
            }     
            // 웅덩이 시작점이 커버되지 않은 경우
            if(coversIndex<water.start){
                coversIndex = water.start;
            }
            int remain = (water.end - coversIndex)%l; // 끝좌표까지 덮기위해 추가로 덮이는 부분
            // 나머지가 0이면 그대로 
            if(remain==0){
                covers += (water.end - coversIndex)/l;
                coversIndex = water.end;
            }
            // 나머지가 0이 아니면 몫+1로 
            else if(remain != 0){
                int plus = (water.end - coversIndex)/l + 1; // 설치한 널판지 개수
                covers += plus;
                coversIndex += l * plus;
            }
        }
        
        System.out.println(covers); // 결과 출력
    }   
}