[C++] 백준 1911번 | 흙길 보수하기

흙길 보수하기

1911번: 흙길 보수하기

---

 

💡스위핑(Sweeping)

스위핑(Sweeping)이란, 어떤 선이나 공간을 한 쪽에서부터 다른 쪽으로 스캔하며 쓸어가는 것이다.

 

✍🏻 풀이

1. 웅덩이의 위치를 정렬해주었다. (앞에서부터 차례대로 쭉 훑기 위해)

2. 현재 좌표를 저장하는 변수인 idx를 선언하였다.

3. 웅덩이의 위치들을 순회하며 현재 위치가 웅덩이의 끝 좌표보다 크면 해당 웅덩이는 건너뛰었다. (이미 널판지를 설치한 웅덩이이기 때문에)

4. 웅덩이의 시작 위치부터 설치할 수 있는 널판지의 개수를 계산해주고, 설치한 마지막 널판지의 끝 좌표 + 1을 idx에 저장해주었다.

5. 설치한 웅덩이의 개수를 cnt에 더해주었다.

---

✅ Accept Code

// baekjoon 1911

#include  <bits/stdc++.h>

using namespace std;

int N, L;
vector<pair<int, int>> pool;

int main() {
    cin >> N >> L;
    for (int i = 0; i < N; i++) {
        int start, end;
        cin >> start >> end;
        pool.push_back({start, end});
    }

    sort(pool.begin(), pool.end());


    int cnt = 0;
    int idx = 0;
    for (int i = 0; i < pool.size(); i++) {
        int start = pool[i].first;
        int end = pool[i].second;
        if (idx >= pool[i].second) continue;

        if (start < idx) start = idx;

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

    }
    cout << cnt;
    return 0;
}