[백준] 1911. 흙길 보수하기 - Python

[Gold V]

 

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

1911번: 흙길 보수하기

 

풀이

간단한 그리디 문제.

 

입력된 물웅덩이를 좌표 순으로 정렬한 이후,

모든 물웅덩이를 순회하며, 널빤지를 설치해야 할 경우에 설치한다.

 

각 순회마다 널빤지의 시작, 끝 좌표를 받고, (line 12)

시작 좌표에 널빤지가 설치되어 있지 않다면, 우선 하나 설치한다. (line 13~15)

그리고, 마지막 좌표를 덮을 때 까지 널빤지를 추가로 설치한다. (line 16~18)

 

AC.

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

pool = []
for _ in range(N):
    pool.append(tuple(map(int, input().split())))
pool = sorted(pool)

# 맨 마지막 널빤지의 시작 좌표.
board = -(L+1)
res = 0

for s, e in pool:
    if board+L-1 < s:
        board = s
        res += 1
        
    while board+L < e:
        board = board+L
        res += 1

print(res)