BOJ 1911 흙길 보수하기

BOJ 백준 1911 흙길 보수하기
C++ JAVA
https://www.acmicpc.net/problem/1911

 

알고리즘을 꾸준히 풀지 않으면 쉽게 풀릴 것 같은 문제조차 어렵게 느껴진다. 꾸준히 풀자!

 

 

문제를 보고 처음 든 생각은 딱히 다른 알고리즘 개념이 있다기보다는 평범한 그리디 문제 같았다.
비슷한 유형으로 [ 1913 회의실 배정 https://www.acmicpc.net/problem/1931 ] 이 생각났음

 

문제를 풀고 난 후 분류를 봤는데 "스위핑" 알고리즘이라는 것이었다.

( 라이님 블로그 참고.. blog.naver.com/kks227/220907708368 )

sweeping에서 유추 가능하듯 전체를 한 번 스캔하면서 작업하는 알고리즘!

 

생각의 흐름
1) (회의실 배정과 같이) 좌표값을 배열에 넣어 정렬해야지
2) 웅덩이 범위가 L로 나뉘지 않으면(diff%L!=0) diff/L의 값에 +1이 필요
3) 널빤지 L의 커버 범위에 따라 그다음 물웅덩이의 시작 위치를 변경해야지 -> 변수 loc

여기까진 평범하게 생각할 수 있었는데

4) 3)에 따라 다음 물웅덩이의 시작 위치를 변경했을 때 (시작>끝) 범위를 체크하지 않아 틀렸다!
-> 정렬을 한번 했다고 해도, 널빤지를 많이 커버해놔서 (시작>끝)이 되어 다음 물웅덩이는 확인하지 않아도 될 경우에는 바로 continue 하는 것이 필요!!

ex) L=3 [1, 8]일 때 널빤지는 9까지 커버해 loc = 10이 되고, 그다음 범위가 [2, 7]이라면 [2, 7]은 넘어가도 된다.

 

C++ 풀이

#include <iostream>
#include <algorithm>
using namespace std;

int N, L;
struct Info{
    int start, end;
};
Info arr[10005];

bool cmp(Info &i1, Info &i2){
    if(i1.start == i2.start) return i1.end < i2.end;
    return i1.start < i2.start;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N >> L;
    
    for(int i=0; i<N; i++)
        cin >> arr[i].start >> arr[i].end;
    
    sort(arr, arr+N, cmp);

    int ans = 0;
    int loc = 0;

    for(int i=0; i<N; i++){
        int x = arr[i].start;
        int y = arr[i].end;
        if(x < loc) x = loc;
        if(x > y) continue;

        int diff = y - x;
        int cnt = diff/L;
        if( diff%L != 0) cnt++;

        ans += cnt;
        loc = x + L*cnt;
    }

    cout << ans << '\n';
    return 0;
}

 

JAVA 풀이

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

public class p1911 {
    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());
        }
        
        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]);
            }            
        });

        int ans = 0; // 필요한 널빤지 갯수
        int loc = 0; // 널빤지 마지막 위치
        for(int i=0; i<N; i++){
            int start = arr[i][0];
            int end = arr[i][1];

            if(start < loc) start = loc;
            if(start > end) continue;

            int diff = end - start;
            int cnt = diff / L;
            if( diff%L != 0 ) cnt++;

            ans += cnt;
            loc = start + cnt*L;
            System.out.println(ans);
        }
        System.out.println(ans);
    }
}