[BOJ] 1911 - 흙길 보수하기 (Python)

 

 

아이디어

 

정렬 후 스위핑으로 덮이지 않은 웅덩이를 덮기 위한 널빤지 최소 개수를 구해 나간다.

 

 

풀이

 

import sys

input = sys.stdin.readline

def solution():
    N, L = map(int, input().split())
    hole = sorted([tuple(map(int, input().split())) for _ in range(N)])
    res = last = 0
    for s, e in hole:
        if e > last:
            if last > s:
                s = last
            cnt = (e-s)//L
            if (e-s)%L:
                cnt += 1
            last = s+L*cnt
            res += cnt
    print(res)

solution()