[C++] 흙길 보수하기 (1911번)

흙길 보수하기

 

 

문제

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

입력

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

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

출력

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

---

문제풀이

이 문제의 중요한 포인트는 널빤지의 길이가 길어 다른 웅덩이 까지 침범한 경우를 생각해야 한다는 것이다.

 

1. 시작지점과 끝 지점을 pair로 저장하는 vector를 생성한다.

2. vector를 시작지점을 기준으로 정렬한다.

3. 정렬한 값을 하나씩 가져와 현재 널빤지가 깔려야 하는 지점을 찾는다.

4. 널빤지가 깔려야 하는 지점으로부터 각 벡터의 끝 지점의 차이를 계산한다.

5. 만약 이 차이 값이 0보다 작다면 이전에 깐 널빤지가 이미 해당 웅덩이를 커버하고 있다는 뜻이므로 다음 값을 가져온다.

6. 차이 값이 0보다 크거나 같은경우는 L로 나누어지는지 안 나누어지는지 확인한다.

7. 나누어진다면 웅덩이 길이와 널빤지 길이가 같다는 뜻이므로 그렇게 값을 넣고 처리한다.

8. 나누어지지 않는다면 웅덩이 길이보다 널빤지를 더 깔아야 한다. 더 깐 지점의 위치를 저장하여 다음 반복문에 사용한다.

 

텍스트로 보면 설명이 조금 아리까리 하다. 포인트를 잘 생각해서 풀어보자.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, l;
    cin >> n >> l;
    vector<pair<int, int>> v;
    for(int i=0; i<n; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back({a, b});
    }
    sort(v.begin(), v.end());

    int now = 0;
    int answer = 0;
    for(int i=0; i<n; i++) {
        if(now < v[i].first)
            now = v[i].first;
        
        int gap = v[i].second - now;

        if(gap < 0) continue;

        if(gap%l == 0) {
            now = v[i].second;
            answer = answer + gap/l;
        }
        else {
            now = now + gap/l * l + l;
            answer = answer + gap/l + 1;
        }
    }
    cout << answer;

    return 0;
}