이번 문제는 그리디 알고리즘을 통해 해결하였다. 우선 웅덩이의 정보를 오름차순으로 정렬해야 한다. 그 이후, 현재 위치를 나타내는 변수 cur을 웅덩이의 첫번째 리스트의 첫번째 인자로 지정해준다. 웅덩이 리스트를 순회하며 만약 cur이 현재 웅덩이의 끝보다 클 경우, 다음 반복으로 넘어간다. 그 외에 cur이 현재 웅덩이의 시작점보다 작을 경우, 시작점으로 갱신해주고, 웅덩이의 끝과 현재 위치 간의 거리가 l로 나눠떨어진다면, 현재 위치를 l을 몫만큼 곱한만큼 증가시켜준다(다리를 놓고 넘어간 것을 구현). 그리고 다리의 갯수를 세는 결과 변수를 몫만큼 증가시킨다. 나눠떨어지지 않을 경우에는 현재 위치를 l을 몫으로 곱한 것에 1을 더한 만큼을 증가시킨다(웅덩이를 넘어서까지 다리를 놓고 넘어간 것을 구현). 그리고 결과 변수를 몫+1만큼 증가시킨다.

이 과정을 모두 마치고 결과변수를 출력하면 결과를 얻을 수 있다.

Code

n, l = map(int, input().split())
pot = [list(map(int, input().split())) for _ in range(n)]
pot.sort()
cur = pot[0][0]
answer = 0
for s, e in pot:
    if cur > e:
        continue
    elif cur < s:
        cur = s
    if (e-cur)%l == 0:
        answer += (e-cur)//l
        cur += ((e-cur)//l) * l
    else:
        answer += (e-cur)//l + 1
        cur += ((e-cur)//l + 1) * l
print(answer)