흙길 보수하기 (1911번) - 백준 (BOJ)

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

1911번: 흙길 보수하기

 

백준 - 흙길 보수하기 (1911번) (Muddy roads)

 

난이도 : Silver 1

알고리즘 : Sorting (정렬)

풀이 소요 시간 : 15 mins

Time Complexity : O( N * logN )

 

import sys
input = sys.stdin.readline


if __name__ == '__main__':
    N, L = map(int, input().split())
    cnt = c = 0
    for s, e in sorted(tuple(map(int, input().split())) for _ in range(N)):
        s = c if s < c else s
        d = e - s
        if not d:
            continue
        t = ((d-1)//L)+1
        cnt += t
        c = t*L + s
    print(cnt)

 

 

웅덩이를 위치에 따라 정렬하고,

널빤지들을 차례대로 덮어가면 해결되는 문제였다.