백준 1911 흙길 보수하기(구현,그리디)

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

1911번: 흙길 보수하기

문제를 읽은 후에 쉬운 문제라고 생각했는데 헷갈릴만한 부분이 많았다.

 

N은 10000개이며 원소는 10억까지 있기 때문에 완전탐색은 불가능했고 

웅덩이의 start, end를 체크하면서 널빤지의 시작 지점을 계속 갱신해가는게 point

 

널빤지를 깔고 나머지가 없으면 완전하게 깔린 것 이니까 l로 나눈 몫 만큼 res에 추가 해주면 되고

나머지가 있으면 널빤지가 남더라도 추가로 1개 깔아줘야 하는데

여기서 만약 널빤지를 깔고 그 후 널빤지의 시작지점이 다음 물웅덩이 시작지점 보다 크다면 

널빤지를 깐 길이만큼 시작지점에 더해줌으로써 갱신해가면서 count를 한다.

n,l = list(map(int,input().split()))
data = []

for _ in range(n):
    data.append(list(map(int,input().split())))
data.sort()

res = 0
start = data[0][0]
for x,y in data:
    temp = 0
    if start < x:
        start = x

    temp = (y-start) // l
    if (y - start) % l:
        temp += 1
    start += temp * l
    res += temp
print(res)