백준 온라인 저지, 그리디 / 1911번: 흙길보수하기 (파이썬 / , 백준 실버문제)

문제

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

입력

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

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

출력

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

제한

예제 입력 1

3 3
1 6
13 17
8 12

예제 출력 1

5

힌트

아래와 같이 5개의 널빤지가 필요하다.

111222..333444555.... // 길이 3인 널빤지
.MMMMM..MMMM.MMMM.... // 웅덩이
012345678901234567890 // 좌표

접근 방법

- 0. 주어진 웅덩이의 좌표는 겹치지 않으므로 웅덩이의 시작 위치가 작은 순으로 오름차순 정렬한다.
- 1. 웅덩이를 하나씩 탐색하며 그 웅덩이를 커버할 수 있는 널판지의 개수를 센다.
- 2. 이때 이전 웅덩이에서 널판지를 걸쳤을 때 현재 탐색 중인 웅덩이까지 조금이라도 커버한다면 그 길이를 계산해주고 널판지를 추가한다. 만약 길이가 닿지 않는다면 해당 널판지의 위치를 현재 웅덩이의 시작 위치로 초기화한다.
- 3. 모든 웅덩이를 탐색한 뒤 총 사용한 널판지의 개수를 출력한다.

코드

# 접근 방법
# 0. 주어진 웅덩이의 좌표는 겹치지 않으므로 웅덩이의 시작 위치가 작은 순으로 오름차순 정렬한다.
# 1. 웅덩이를 하나씩 탐색하며 그 웅덩이를 커버할 수 있는 널판지의 개수를 센다.
# 2. 이때 이전 웅덩이에서 널판지를 걸쳤을 때 현재 탐색 중인 웅덩이까지 조금이라도 커버한다면 그 길이를 계산해주고 널판지를 추가한다. 만약 길이가 닿지 않는다면 해당 널판지의 위치를 현재 웅덩이의 시작 위치로 초기화한다.
# 3. 모든 웅덩이를 탐색한 뒤 총 사용한 널판지의 개수를 출력한다.
import sys
input = sys.stdin.readline

n, l = map(int, input().split())
pool = [list(map(int, input().split())) for _ in range(n)]
pool.sort(key=lambda x: x[0])
plank = pool[0][0]
total_count = 0
for start, end in pool:
    if plank > end:
        continue
    elif plank < start:
        plank = start
    dist = end - plank
    remainder = 1
    if dist % l == 0:
        remainder = 0
    count = dist // l + remainder
    plank += count * l
    total_count += count
print(total_count)