[백준/1911] 흙길 보수하기 (Python)

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

1911번: 흙길 보수하기

 

Difficulty : Gold 5

 

Status : Solved

 

Time : 00:15:58

 

---

 

문제 설명

 

 

어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N(1 ≤ N ≤ 10,000)개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이가 L(1 ≤ L ≤ 1,000,000)인 널빤지들을 충분히 가지고 있어서, 이들로 다리를 만들어 물웅덩이들을 모두 덮으려고 한다. 물웅덩이들의 위치와 크기에 대한 정보가 주어질 때, 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 구하여라.

 

 

입력 및 출력

 

입력

 

첫째 줄에 두 정수 N과 L이 들어온다.

둘째 줄부터 N+1번째 줄까지 총 N개의 줄에 각각의 웅덩이들의 정보가 주어진다. 웅덩이의 정보는 웅덩이의 시작 위치와 끝 위치로 이루어진다. 각 위치는 0 이상 1,000,000,000 이하의 정수이다. 입력으로 주어지는 웅덩이는 겹치지 않는다.

 

출력

 

첫째 줄에 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 출력한다.

 

입력 예시

 

3 3
1 6
13 17
8 12

 

출력 예시

 

5

 

 

---

 

풀이

 

그리디하게 생각해보자. 웅덩이가 서로 겹치지 않으니, 단순 정렬로 웅덩이 좌표를 정렬하자.

이전의 마지막 널빤지의 끝점 좌표를 prev라고 두면, (s, e) 좌표를 가진 어느 웅덩이에 대해 다음 경우들이 발생한다.

 

• prev가 s보다 작다면, 이는 이전 널빤지가 전혀 현재 웅덩이에 관여하지 못한다는 사실을 의미한다. 따라서 prev = s로 보정하여도 지장이 없다.
• 만약 prev >= e라면, 이전 널빤지가 현재 웅덩이를 전부 커버할 수 있다는 의미이다. 따라서 널빤지를 추가로 놓을 필요가 없다.
• 만약 prev < e라면 널빤지로 웅덩이를 추가로 덮어야 함을 의미한다. 이 때 필요한 널빤지는 ceil((e - prev) / L)이 필요하다. 이에 맞추어 최종 결과값과 prev를 업데이트한다. 

 

풀이 코드

import math
import sys
input = sys.stdin.readline

N, L = map(int, input().split())
hole_list = sorted([list(map(int, input().split())) for _ in range(N)])
prev = -L-1
answer = 0

for s, e in hole_list :
  if prev < s :
    prev = s
  if prev < e :
    tmp = math.ceil((e - prev) / L)
    answer += tmp
    prev += L*tmp
    
print(answer)

풀이완료!