✔️ 문제에 나와 있는 힌트
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)