1911번 흙길 보수하기

https://www.acmicpc.net/problem/1911

---

아이디어

+) 옛날에 풀었던 문제인데도 어려웠다. 언젠가 다시 한 번 봐야겠다...

1. 웅덩이 좌표를 시작 위치를 기준으로 오름차순 정렬한다.

2. 반복문으로 웅덩이를 하나씩 보면서, 커버할 수 있는 널빤지의 개수를 센다.
   2-1. 널빤지의 시작 지점이 start 지점보다 작으면 널빤지를 다시 시작해야하므로 널빤지를 새로 갱신한다.(elif 부분)
   2-2. 이전 웅덩이에서 널빤지를 걸쳤을 때, 현재 탐색 중인 웅덩이까지 조금이라도 커버할 수도 있으니 그 길이(dist)를 (웅덩이 종료 지점) - (널빤지 시작 지점) 계산하고 널빤지를 추가한다.

---

코드

N, L = map(int, input().split()) # 웅덩이 개수, 널빤지 길이
ground = [list(map(int, input().split())) for _ in range(N)]
ground.sort(key=lambda x:x[0]) #시작지점 기준으로 정렬

answer = 0 # 널빤지 개수
current = ground[0][0]
for start, end in ground:
    if current > end: continue # 널빤지 시작이 end보다 작으면 당연히 덮음
    elif current < start: # 널빤지 시작 지점 갱신
        current = start

    dist = end - current # 널빤지가 필요한 거리
    rest = 1    # 여분
    if dist % L == 0: rest = 0 # 널빤지 딱 맞으면 여분 필요X

    cnt = dist // L + rest  # 해당 구간에서 필요한 널빤지
  	current += cnt*L  # 널빤지 시작 지점 갱신
  	answer += cnt
   
print(answer)