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

백준 흙길 보수하기 1911번 C++ 풀이

문제

비가 내려 흙길 위에 여러 개의 물웅덩이가 생겼습니다. 월드학원에서는 길이가 L인 널빤지를 충분히 가지고 있습니다. 목표는 모든 물웅덩이를 최소 개수의 널빤지로 덮는 것입니다.

• 입력
  * 첫 줄에 웅덩이 개수 N과 널빤지 길이 L이 주어집니다.
  * 다음 줄부터 N개의 웅덩이 정보가 주어지며, 각 줄에는 웅덩이의 시작 위치와 끝 위치가 들어옵니다.
  * 웅덩이들은 겹치지 않습니다.


• 출력
  * 모든 웅덩이를 덮기 위해 필요한 널빤지의 최소 개수를 출력합니다.

---

테스트케이스

입력

3 3
1 6
13 17
8 12

출력

5

해석

* 웅덩이 [1, 6] 은 길이 5 → 널빤지 2개 필요
* 웅덩이 [8, 12] 은 길이 4 → 널빤지 2개 필요
* 웅덩이 [13, 17] 은 길이 4 → 널빤지 2개 필요처럼 보이지만, [8, 12]의 덮은 범위 끝이 14까지 커버되므로 추가 1개만 필요
* 총합 = 5개

---

작동원리

조건

• N = 3
• L = 3
• 웅덩이: [1,6], [8,12], [13,17]
• 좌표는 0부터 17까지 사용합니다.

---

1. 초기 상태

아직 널빤지를 놓지 않은 상태입니다.
웅덩이 구간은 M으로 표시하고, 땅은 -로 표시합니다.

idx :  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
arr :  -  M  M  M  M  M  -  -  M  M  M  M  M  M  -  -  -  -

설명: [1,6] 구간에 물이 있으므로 1~5까지 M
[8,12] 구간에 물이 있으므로 8~12까지 M
[13,17] 구간에 물이 있으므로 13~16까지 M

---

2. 첫 번째 웅덩이 [1,6] 처리

(1) 첫 번째 널빤지 배치

널빤지 길이는 3입니다.
웅덩이 시작점 1부터 덮기 시작합니다.
좌표 [1,2,3]을 널빤지로 덮습니다.

idx :  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
arr :  -  X  X  X  M  M  -  -  M  M  M  M  M  M  -  -  -  -

설명: 웅덩이의 일부(1~3)를 X로 바꾸어 덮었습니다. 아직 4~5는 남아있습니다.

---

(2) 두 번째 널빤지 배치

남은 웅덩이 부분은 [4,5]입니다.
좌표 [4,5,6]에 널빤지를 하나 더 놓습니다.
6은 사실 땅이지만, 널빤지 길이가 3이라 함께 덮입니다.

idx :  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
arr :  -  X  X  X  X  X  X  -  M  M  M  M  M  M  -  -  -  -

설명: 이제 첫 번째 웅덩이 [1,6] 전체가 완전히 덮였습니다.
필요한 널빤지 수는 2개입니다.

---

3. 두 번째 웅덩이 [8,12] 처리

(1) 첫 번째 널빤지 배치

웅덩이 시작점은 8입니다.
좌표 [8,9,10]을 널빤지로 덮습니다.

idx :  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
arr :  -  X  X  X  X  X  X  -  X  X  X  M  M  M  -  -  -  -

설명: 웅덩이 [8,12] 중 8~10을 덮었습니다.
아직 11~12가 남아있습니다.

---

(2) 두 번째 널빤지 배치

좌표 [11,12,13]에 널빤지를 놓습니다.
이렇게 하면 웅덩이 [8,12]의 나머지 부분(11,12)이 모두 덮이고, 13은 다음 웅덩이의 시작을 일부 겹쳐 덮게 됩니다.

idx :  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
arr :  -  X  X  X  X  X  X  -  X  X  X  X  X  X  -  -  -  -

설명: 두 번째 웅덩이 [8,12]는 널빤지 2개로 완전히 덮였습니다.
그리고 우연히 세 번째 웅덩이의 시작점 13도 일부 덮였습니다.

---

4. 세 번째 웅덩이 [13,17] 처리

현재 13은 이미 덮였습니다. 따라서 남은 구간은 [14,15,16]입니다.

(1) 널빤지 배치

좌표 [14,15,16]에 널빤지를 하나 놓습니다.

idx :  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
arr :  -  X  X  X  X  X  X  -  X  X  X  X  X  X  X  X  X  -

설명: 세 번째 웅덩이 [13,17]도 이제 완전히 덮였습니다.
필요한 널빤지는 단 1개입니다.

---

5. 최종 결과

• 첫 번째 웅덩이 [1,6] → 널빤지 2개
• 두 번째 웅덩이 [8,12] → 널빤지 2개
• 세 번째 웅덩이 [13,17] → 널빤지 1개
• 총합 = 5개

최종적으로 모든 M이 X로 바뀌어 웅덩이가 전부 덮였습니다.

---

아이디어

1. 웅덩이 구간을 시작점 기준으로 정렬
   
   • 입력받은 웅덩이 [x1, x2]들을 시작 좌표 기준으로 오름차순 정렬합니다.
   • 이렇게 해야 앞에서부터 차례대로 덮어 나갈 수 있습니다.


2. cover의 의미 정의
   
   • cover는 지금까지 널빤지로 덮은 마지막 위치 바로 다음 좌표를 의미합니다.
   • 즉, cover = 7이라면 “0~6까지는 이미 덮였고, 7부터는 아직 안 덮였다”라는 뜻입니다.


3. 웅덩이를 처리할 때 조건 분기
   
   • 각 웅덩이 [x1, x2]를 순서대로 확인합니다.
   • 두 가지 경우로 나뉩니다.

   1. cover ≤ x1 : 웅덩이 시작점이 아직 덮이지 않았다면, 웅덩이 시작점 x1부터 널빤지를 놓기 시작합니다.
   2. cover > x1 : 웅덩이 시작점이 이미 덮였다면, cover 위치에서부터 남은 구간만 덮습니다.



4. 필요한 널빤지 개수 계산
   
   • 현재 덮어야 할 길이를 계산합니다.

   case1: cover ≤ x1 → 덮어야 할 길이 = \((x_2 - x_1)\)
   case2: cover > x1 → 덮어야 할 길이 = \((x_2 - \text{cover})\)

   • 필요한 널빤지 수 = \(\lfloor\frac{\text{덮어야 할 길이} + L - 1}{L}\rfloor\)

   즉, 길이를 L로 나눈 몫에 올림 처리.



5. cover 업데이트
   
   • 널빤지를 배치한 뒤,

   case1 → cover = x1 + (필요한 널빤지 수 × L)
   case2 → cover = cover + (필요한 널빤지 수 × L)



6. cnt 증가
   
   • 매번 구한 널빤지 개수를 cnt에 더합니다.
   • 모든 웅덩이를 처리한 후 cnt를 출력하면 최소 널빤지 수가 됩니다.

---

예제 조건

• N = 3, L = 3
• 웅덩이: [1,6], [8,12], [13,17]
• 좌표: 0 ~ 17

---

1. 초기 상태

idx :  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
arr :  -  M  M  M  M  M  -  -  M  M  M  M  M  M  -  -  -  -
cover: ↑
cnt = 0

설명: 아직 아무것도 덮지 않았으므로 cover=0, cnt=0입니다.
웅덩이 [1,6] 시작=1, cover(0) ≤ x1(1) → x1에서 시작.

---

2. 첫 번째 웅덩이 [1,6]

(1) 첫 번째 널빤지 [1~3]

idx :  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
arr :  -  X  X  X  M  M  -  -  M  M  M  M  M  M  -  -  -  -
cover:           ↑
cnt = 1

설명: 웅덩이 시작점 1에서 시작, 널빤지 1개 사용.
cover=4로 갱신, cnt=1.

---

(2) 두 번째 널빤지 [4~6]

idx :  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
arr :  -  X  X  X  X  X  X  -  M  M  M  M  M  M  -  -  -  -
cover:               ↑
cnt = 2

설명: 웅덩이 끝까지 덮지 못했으므로 cover=4에서 이어서 시작.
널빤지 1개 더 사용, cover=7, cnt=2.

---

3. 두 번째 웅덩이 [8,12]

(1) 첫 번째 널빤지 [8~10]

idx :  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
arr :  -  X  X  X  X  X  X  -  X  X  X  M  M  M  -  -  -  -
cover:                     ↑
cnt = 3

설명: cover=7, 웅덩이 시작=8, cover ≤ x1 → x1에서 시작.
[8~10] 덮고 cover=11, cnt=3.

---

(2) 두 번째 널빤지 [11~13]

idx :  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
arr :  -  X  X  X  X  X  X  -  X  X  X  X  X  X  -  -  -  -
cover:                           ↑
cnt = 4

설명: cover=11, 웅덩이 끝=12, 아직 미덮임 → cover에서 이어서 시작.
[11~13] 덮고 cover=14, cnt=4.

---

4. 세 번째 웅덩이 [13,17]

(1) 널빤지 [14~16]

idx :  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
arr :  -  X  X  X  X  X  X  -  X  X  X  X  X  X  X  X  X  -
cover:                                   ↑
cnt = 5

설명: cover=14, 웅덩이 시작=13, cover > x1 → 웅덩이 시작은 이미 덮였으므로 cover에서 시작.
[14~16] 덮고 cover=17, cnt=5.

---

5. 최종 정리

• [1,6] → 널빤지 2개 (cnt=2)
• [8,12] → 널빤지 2개 (cnt=4 누적)
• [13,17] → 널빤지 1개 (cnt=5 누적)
• 총 널빤지 수 = 5개

---

전체코드

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

struct Point {
    int x1;
    int x2;

    bool operator<(const Point& other) const {
        return x1 < other.x1;
    }
};

int main(void) {
    int N, L, cnt = 0;
    Point arr[10000];
    cin >> N >> L;

    for (int i = 0; i < N; i++) {
        int x, y;
        cin >> x >> y;
        arr[i] = {x, y};
    }

    sort(arr, arr + N);

    int cover = 0, len = 0;

    for (int i = 0; i < N; i++) {
        if (cover > arr[i].x1) {  
            len = (arr[i].x2 - cover + L - 1) / L;
            cover = cover + len * L;
        } else {  
            len = (arr[i].x2 - arr[i].x1 + L - 1) / L;
            cover = arr[i].x1 + len * L;
        }
        cnt += len;
    }

    cout << cnt << endl;
    return 0;
}

---

결론

문제의 핵심은 겹치지 않는 웅덩이들을 정렬한 뒤, 현재 덮인 범위(cover)를 관리하면서 남은 구간만 널빤지로 덮는 것입니다.
이렇게 하면 불필요한 널빤지 낭비 없이, 최소 개수를 구할 수 있습니다.
시간 복잡도는 O(N log N)으로 충분히 효율적입니다.