흙길 보수하기

문제

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

입력

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

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

출력

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

해결

1. [[시작점, 끝점], [시작점, 끝점], ...] 으로 입력받은 후에 시작점 기준으로 내림차순 정렬
2. count -> 판자 개수, last_index -> 지난 과정에서 초과된 판자의 가장 왼쪽 위치
3. 시작점 끝점으로 for문 시작
4. 만약 판자가 이미 현재 구역의 웅덩이를 다 덮은 경우 continue
5. 만약 판자가 현재 구역의 웅덩이를 일부분 덮은 경우 end를 last_index 설정
6. 판자로 정확하게 현재 구역의 웅덩이를 덮을 수 있는 경우 + (구역의 길이 // 판자 길이), last_index를 start로 설정
7. 판자가 구역을 넘어가는 경우 + (구역의 길이 // 판자 길이 + 1), last_index를 start - 판자길이 + 남은길이

코드

n, l = map(int, input().split())

sand = []
for i in range(n):
    start, end = map(int, input().split())
    sand.append([start, end])

## 제일 뒤부터로 정렬
sand.sort(key = lambda x:x[1], reverse=True)

count = 0
last_index = sand[0][1]

for start, end in sand:
    if last_index < start: # 이미 판자가 덮은 경우
        continue
    if last_index < end: # 판의 길이가 넘어왔을때
        end = last_index
    len = end - start
    remain = len % l
    if remain == 0: # 판자로 정확히 덮을 수 있는 경우
        last_index = start
        count += len // l
    else: # 판자가 남는경우
        last_index = start - l + remain
        count += len // l + 1

print(count)