📚 1911 - 흙길 보수하기

흙길 보수하기

이해

✔️ 문제에 나와 있는 힌트

111222..333444555.... // 길이 3인 널빤지
.MMMMM..MMMM.MMMM.... // 웅덩이
012345678901234567890 // 좌표

문제에서는 웅덩이의 시작 위치와 끝 위치를 입력으로 주어진다.

3 3
1 6
13 17
8 12

그러므로, 1 ~ 5, 8 ~ 11, 13 ~ 16 으로 웅덩이가 위치를 이룬다.

문제 자체가 어떠한 알고리즘으로 풀어야할 지 감이 안올 때는, 그리디 알고리즘 문제인지 의심해봐야 한다.

✔️ 문제 규칙
(1) 웅덩이가 L 배수 길이 만큼 위치를 이룬다면, 현재 웅덩이 (도착 - 시작) 거리 / L배수를 하여 널빤지 개수를 구한다.
(2) 웅덩이가 L 배수 길이 만큼 위치를 차지하지 않는다면

• 현재 웅덩이 (도착 - 시작) 거리 / L배수 + 1을 한다. (남은 나머지 공간에 널빤지가 하나 더 필요하다.)
• 만약, 널빤지가 다음 웅덩이 위치까지 덮었을 경우를 생각해야 한다.
  • 이때는, 다음 웅덩이 시작 위치를 널빤지가 덮은 마지막 인덱스의 다음 인덱스로 지정하면 된다.

소스

import sys

read = sys.stdin.readline

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

puddle = []

for _ in range(n):
    sta, arri = map(int, read().split())
    puddle.append([sta, arri])

puddle.sort()
answer = 0

for i in range(n):
    left, right = puddle[i]
    t = (right - left) % l
    if t:
        length = (right - left) // l + 1  # 웅덩이를 다 덮지 못하는 경우 1개를 추가한다.
    else:
        length = (right - left) // l  # 웅덩이가 딱 맞는 경우

    answer += length
    arrival = left + length * l
    # 마지막 위치가 아닐 때
    if (i + 1) < n:
        if arrival > puddle[i + 1][0]:
            puddle[i + 1][0] = arrival  # 널빤지가 웅엉이를 초과해서 다음 웅덩이 까지 덮는 경우

print(answer)