[Algorithm] 백준 1911 : 흙길 보수하기

문제

어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N (1 <= N <= 10,000) 개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이 L (L은 양의 정수) 짜리 널빤지들을 충분히 가지고 있어서, 이들로 다리를 만들어 물웅덩이들을 모두 덮으려고 한다. 물웅덩이들의 위치와 크기에 대한 정보가 주어질 때, 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 구하여라.

---

입력

첫째 줄에 N과 L이 들어온다.

둘째 줄부터 N+1번째 줄까지 총 N개의 줄에 각각의 웅덩이들의 정보가 주어진다. 웅덩이의 정보는 웅덩이의 시작 위치와 끝 위치로 이루어진다. 각 위치는 0이상 1,000,000,000이하의 정수이다.

---

출력

첫째 줄에 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 출력한다.

---

풀이

보통은 하나의 웅덩이에 사용되는 널빤지의 개수를 세면 되겠지만 한가지 예외가 생각났습니다.
바로 널빤지가 하나의 웅덩이를 넘어 다음 웅덩이에 걸치는 경우입니다.

.	1	1	1	2	2	2	.	.	3	3	3	4	4	4	5	5	5	.	.	.
.	O	O	O	O	O	O	.	.	O	O	O	O	.	O	O	O	O	.	.	.

위 표에서 4번 널빤지같은 경우가 바로 위에서 말한 경우가 되겠죠

이를 어떻게 코드로 표현할 지 생각해보다가 다음과 같은 방법을 생각했습니다.

1. 웅덩이들의 좌표를 정렬한다.
2. 웅덩이[0].first 부터 웅덩이[0].second까지 널빤지만큼 반복하여 더한다.
3. 웅덩이[0].second를 넘어갔을 때 그 시점을 가지고있는다.
4. 가지고 있던 시점을 웅덩이[1].first와 비교하여 시점이 이보다 크거나 같을 경우 웅덩이[1].first를 대신하여 시점을 사용한다.
5. 다시 2번으로 돌아가면서 반복한다.

단순하게 한번만 생각하고 풀어서 최적의 코드는 아닙니다.
별도의 수식을 가미하거나 더 효율적인 방법을 사용하여 시간을 단축할 수도 있겠죠😅

---

코드

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N, L, start, end;
    scanf("%d %d", &N, &L);
    vector<pair<int,int>> v;

    for (int i = 0; i < N; ++i) {
        scanf("%d %d", &start, &end);
        v.push_back(pair<int,int>(start, end));
    }

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

    int count{0};
    int upcnt{0};
    for (int i = 0 ; i < v.size(); i++) {
        if(v[i].first > upcnt)
            upcnt = v[i].first;

        while(upcnt < v[i].second) {
            upcnt += L;
            count++;
        }
    }
    printf("%d", count);
}