[Python] 1911번: 흙길 보수하기

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

---

그리디 문제

각 웅덩이마다 널빤지를 놓는 시작점이 되는 now를 갱신한다

첫 웅덩이 pool[0] 의 시작점 [0][0]로 now를 초기화하고

end-now로 거리를 계산하여 널빤지 길이인 L로 나누어 나머지가 남는 경우(=추가로 1개 더 필요)와 안 남는 경우를 나누어 생각한다.

now에 총 널빤지 길이를 더하는 부분을 주의

N,L = map(int, input().split())
pool = [list(map(int,input().split())) for _ in range(N)]
pool.sort()
now = pool[0][0]
total = 0
for start,end in pool:
    if now > end:
        continue
    elif now < start:
        now = start
    dist = end - now
    remain = 1
    if dist % L == 0:
        remain = 0
    cnt = dist//L + remain
    now += cnt * L
    total += cnt
print(total)