BOJ 1911 - 흙길 보수하기

www.acmicpc.net/problem/1911

1911번: 흙길 보수하기

 

딱히 큰 설명이 필요한 문제는 아닌것 같다

각 물웅덩이의 좌표를 담아서 오름차순 정렬한뒤, 

물웅덩이 범위 내에 있으면 판자를 놓고 다음 좌표를 넘어갈때, L 만큼 넘어가면 된다

N 의 최대가 10000 이므로 시간복잡도에 유의해야한다.

 

 

- C++

#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
int N, L, answer;
vector<pair<int, int>> pools;
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N >> L;
    for (int i = 0; i < N; ++i) {
        int start, end;
        cin >> start >> end;
        pools.push_back({start, end});
    }
    
    sort(pools.begin(), pools.end());
    
    int next = 0;
    for (int i = 0; i < pools.size(); ++i) {
        if (next < pools[i].first) next = pools[i].first;
        
        while(next < pools[i].second) {
            next += L;
            answer++;
        }
    }
    
    cout << answer;
    
    return 0;
}