백준 1911번: 흙길 보수하기(Python)

흙길 보수하기 

문제

 

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

입력

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

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

출력

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

예제 입력 1

3 3
1 6
13 17
8 12

예제 출력 1

5

 

이 문제는 실버의 난이도로, 중요한 건 물웅덩이는 겹치지 않는다는 점과 널빤지의 크기와 물웅덩이끼리의 거리에 따라서 널빤지가 이어질 수도 있다는 점이다.

 

 

코드

import sys
input = sys.stdin.readline

n,l = map(int,input().split())
#이차원 배열에 데이터 입력
puddles=[(list(map(int,input().split()))) for _ in range(n)]
#puddels[0][]기준으로 오름차순 정렬
puddles.sort(key=lambda x : x[0])
result=0
boundary=puddles[0][0]
for start, end in puddles:
    if start>boundary:
        boundary=start
    diff = end-boundary
    if diff%l == 0:
        count=diff//l
        boundary=end
    else:
        count=diff//l+1
        boundary=end+(l-diff%l)
    result+=count
print(result)

일단 데이터들을 puddles[][]에 넣고, 정렬한다. 널빤지가 초과했을 때를 위하여 boundary로 더 덮어야하는 부분 diff를 구하는 방법으로 짰다.

 

코드를 짜며 boundary의 초기화를 제대로 하지 않아서 오류가 여러 번 났었다. 변수 초기화를 잘 생각해야겠다.

sys.stdin.readline을 쓰지 않았을 때는 168ms가 나왔었는데, 쓰니까 40ms로 약 4배차이가 났다. 다시금 input()과의 속도의 차이를 체감했다.