BOJ 1911 - 흙길 보수하기

문제 링크

그리디 알고리즘 문제이다.
시작지점 순서로 정렬한 후에 웅덩이를 덮고 어디까지 덮었는지를 체크하면서 계속 덮어나가면 된다.
새로 덮어야 할 경우와 이미 일부분이 덮인 경우를 따로 처리해야 한다.

puddles = []
N, L = map(int, input().split())
for _ in range(N):
    x, y = map(int, input().split())
    if x < y:
        puddles.append((x, y))
    else:
        puddles.append((y, x))

puddles.sort()
answer = 0
covered = -1
for (x, y) in puddles:
    # 아예 새로 덮어야 하는 경우
    if x >= covered:
        dist = y-x
        required = dist//L if dist % L == 0 else (dist//L)+1
        answer += required
        covered = x+(required*L)

    # 일부분이 덮인 경우
    else:
        dist = y-covered
        required = dist//L if dist % L == 0 else (dist//L)+1
        answer += required
        covered = covered+(required*L)

    #print("covered", covered)

print(answer)