[Python/파이썬] 백준 1911번 흙길 보수하기

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

 

코드

from math import ceil
import sys
input = sys.stdin.readline

n, l = map(int, input().split())
woongs = []
for _ in range(n):
    s, e = map(int, input().split())
    woongs.append((s, e))

woongs.sort()

ans = 0
prev = -1_000_000
for i in range(n):
    if prev <= woongs[i][0]:
        prev = woongs[i][0]
    num = ceil((woongs[i][1]-prev)/l)
    ans += num
    prev = prev + num*l
print(ans)

 

prev는 이전에 깔았던 널빤지 중 가장 끝의 널빤지의 끝 위치이다. 그렇기 때문에 prev가 현재 웅덩이의 시작위치보다 오른쪽이라면 prev에서부터 이어서 널빤지를 더 깔면 되고, 아니라면 현재 웅덩이의 시작 위치부터 깔아주면 되는데 계산을 편하게 하기 위해서 prev가 현재 웅덩이의 시작위치보다 왼쪽이거나 같은 경우에는 prev 값을 현재 웅덩이의 시작 위치로 바꿔주었다.

 

i번째 웅덩이를 덮을 수 있는 널빤지의 개수는 prev부터 웅덩이의 끝(woongs[i][1])까지의 거리를 l로 나눈 값을 정수자리까지 올림한 수다.