(C++) - 백준(BOJ) 1911 : 흙길 보수하기

www.acmicpc.net/problem/1911

1911번: 흙길 보수하기

sweeping 문제였습니다.

 

풀이방법

 1. 웅덩이들의 좌표를 오름차순으로 정렬해줍니다.

 

 2. 물웅덩이의 좌표들을 모두 확인하면서 다음을 수행합니다.

   2-1. x좌표부터 시작해 만약 x를 넘어가는 물웅덩이의 끝 좌표가 있고 시작점이 x보다 크다면 x를 해당 웅덩이의 시작점으로 갱신해줍니다. 

   2-2. 이 후 널판지에 개수를 구합니다. 

   2-3. 정답에 더해준 뒤 x의 마지막 좌표를 마지막 널판지를 놓은 자리의 끝으로 갱신해줍니다.

 

 3. 정답을 출력합니다.

   

 

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int n, l, ans, x;
vector <pii> waterHole;
int main(){
    cin >> n >> l;
    while(n--){
        int x,y;
        cin >> x >> y;
        waterHole.push_back({x,y});
    }
    sort(waterHole.begin(),waterHole.end());

    for(auto &w : waterHole){
        if (x >= w.second) continue;
        x = max(x, w.first); 
        int cnt = (w.second - (x + 1)) / l + 1; 
        ans += cnt; 
        x += l * cnt; 
    }
    cout << ans << '\n';
}