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

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

1911번: 흙길 보수하기

import sys
import math
input = sys.stdin.readline

N, L = map(int, input().split())

pools = []
for _ in range(N):
    pools.append(list(map(int, input().split())))
pools.sort(key=lambda x: x[0])

plankCount = 0
maxPlankIndex = 0

for s, e in pools:
    if s <= maxPlankIndex:
        s = maxPlankIndex+1

        if e <= s:
            continue

    curPlankCount = math.ceil((e-s)/L)
    plankCount += curPlankCount
    maxPlankIndex = max(maxPlankIndex, s + curPlankCount*L-1)

print(plankCount)

우선 입력받은 웅덩이들을 시작점 기준으로 정렬한다.

이후에 정렬된 pools를 돌면서, 현재의 웅덩이 길이를 기준으로 curPlankCount를 구하고, 최종적으로 출력할 plankCount에 더해준다.

if문에 대해 설명하기 전에 서술하자면, maxPlankIndex는 판자가 채워진 마지막 인덱스를 저장해주는 변수이다. 현재 물웅덩이의 시작 지점이 maxPlankIndex 이상이면 s를 maxPlankIndex+1로 설정해준다. 가령, 7까지 널빤지가 채워져있는데, 이번 웅덩이의 s가 5이면, s를 8로 바꿔준다는 것이다. 이렇게 s를 설정하였는데 e보다 클 경우 널빤지 추가 연산을 하지 않고 넘어간다.