[백준] 1911번 흙길 보수하기

💡문제접근

• 정해진 길이의 물웅덩이를 넘어서는 널빤지가 그 다음 물웅덩이의 시작점이거나 시작점을 넘어서는 지점일 수 있으므로 최솟값을 구하려면 그 다음 널빤지의 시작점과 기존 물웅덩이의 도착점을 비교해 시작점을 갱신하고 널빤지의 최소 개수를 구하면 된다.

💡코드(메모리 : 32140KB, 시간 : 64ms)

import sys
input = sys.stdin.readline

N, L = map(int, input().strip().split())
lst = []
for _ in range(N):
    S, E = map(int, input().strip().split())
    lst.append([S, E])
lst.sort(key=lambda x : x[0])

cnt = 0
next_pos = 0
flag = True
for start, end in lst:
    start = max(start, next_pos)
    if (end - start) % L == 0:
        flag = True
        cnt += (end - start) // L
    else:
        flag = False
        cnt += ((end - start) // L) + 1
    if flag:
        next_pos = start + L * ((end - start) // L)
    else:
        next_pos = start + L * (((end - start) // L) + 1)
print(cnt)

💡소요시간 : 27m