백준 흙길 보수하기 1911번 파이썬

백준 흙길 보수하기 1911번 파이썬 풀이

문제

비가 내려 흙길 위에 여러 개의 물웅덩이가 생겼습니다. 월드학원에서는 길이가 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개

---

아이디어

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개

---

전체코드

N,L = map(int,input().split())
arr=[]

for i in range(N):
    arr.append(list(map(int,input().split())))

arr.sort()

cover=0
cnt=0
for i in range(N):
    if arr[i][0]<cover:
        lenK=(arr[i][1]-cover+L-1)//L
        cover=cover+(L*lenK)
    else:
        lenK=(arr[i][1]-arr[i][0]+L-1)//L
        cover=arr[i][0]+(L*lenK)
    cnt += lenK

print(cnt)  

---

결론

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