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

문제

난이도 : 골드 5 백준 1911번 : 흙길 보수하기

코드

#include <bits/stdc++.h>

using namespace std;

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

int main()
{
    cin >> N >> L;

    int nul = 0;
    int answer = 0;

    for (int i = 0; i < N; i++)
    {
        int l, r;
        cin >> l >> r;

        v.push_back({ l, r });
        
    }
    
    sort(v.begin(), v.end());

    for (int i = 0; i < N; i++)
    {
        nul = max(nul, v[i].first);

        while (nul < v[i].second)
        {
            nul += L;
            answer++;
        }
    }


    cout << answer;

    return 0;
}

풀이

라인 스위핑 문제
물웅덩이의 위치가 0에서 10억까지 이므로 배열은 못 쓰는 문제
물 웅덩이의 위치를 pair<int, int>로 저장했다. 이 때 라인스위핑을 위해 물웅덩이의 시작 위치로 오름차순 정렬해줬다.
nul 변수를 선언해 널빤지의 끝 부분을 나타냈다. 그래서 매 반복문마다 nul과 물 웅덩이의 시작 부분을 비교해서 큰 값을 nul 변수에 담았다. 최종 설명은 나중에
nul 변수가 물 웅덩이의 끝보다 커질 때 까지 L씩 더해간다.
그림을 그려보면서 풀어서 설명이 어려울 수 있는데 물 웅덩이의 시작부터 끝까지 널빤지를 채워야 하는건 확실하다. 이때 L이 길 경우 널빤지를 물 웅덩이의 끝 지점을 넘을 수 있다.
널빤지를 물 웅덩이의 끝 지점을 넘게 붙였는데 그 다음 물 웅덩이의 시작보다도 넘게 붙였으면 그 다음 널빤지를 붙이는 지점이 nul 이다.
솔직히 설명이 너무 어렵다 ㅜㅠㅠ

결과