🤔 접근
글이 짧은 문제들이 정말 좋은 것 같다. (독해력이 안 좋아서)
이 문제는 아주 간단한 그리디 문제다. 그리디나 구현 문제들을 풀 때 혼자 상황 가정하고 중얼중얼 거리면서 푸는데 이게 좀 도움이 되는 것 같다. 그런데, 좌표를 공간으로 생각하고 풀지 아니면 한 점으로 생각하고 풀지 확실히 정하고 시작했어야 덜 헷갈렸을 것 같다. 나는 공간으로 생각하고 풀었다.
-
좌표가 0인 지점부터 판자를 갖고 건너간다고 생각하면서 구현해보자.
- 그렇다면 웅덩이들의 정보가 시작점을 기준으로 정렬되어 있어야겠구나
- 정렬 후 웅덩이를 for 문으로 하나씩 확인하면서 판자를 설치해보자
- 판자가 어디까지 설치되어 있는지 end라는 변수에 저장해놓자
-
(for문) 새로운 웅덩이를 마주쳤을 때
웅덩이가 시작하는 지점에 현재 판자가 놓여 있는지 여부가 중요하다. 없다면 새로운 판자를 웅덩이 시작점부터 설치해야 할 것이고, 있다면 이전 웅덩이 때문에 설치했던 판자가 다음 웅덩이에 영향을 주는 것이기 때문이다.end = 마지막 판자 위치 a = 웅덩이 시작점 b = 웅덩이 끝나는 지점 (i[1] - 1) water = 웅덩이 너비 (b - 1 + 1)1) end >= a
웅덩이 시작은 a지만 end지점까지는 이미 판자가 설치되어 있으니, 시작점을 a = end+1 으로 바꿔주자.
2) end < b:
웅덩이가 작으면 이전 판자에 의해 웅덩이가 끝나는 지점 b가 end보다 작을수도 있다. 이런 경우 무시하면 되기 때문에 end<b인 경우만 고려하면 된다. 이땐 웅덩이의 크기만큼 판자를 깔아주자. 그리도 당연히 깔아준 만큼 end와 count 를 늘려주면 끝!
💻 코드
# 1911
import sys
input = sys.stdin.readline
n, l = map(int, input().split())
arr = []
for _ in range(n):
a, b = map(int, input().split())
arr.append((a, b))
arr.sort()
#마지막 판자 지점, 판자 개수
end, count = 0, 0
for i in arr:
a, b = i[0], i[1]-1
# 이전 판자가 영향을 주는 경우
if end >= a:
a = end+1
if end < b:
# 판자 몇 개면 돼?
water = b - a + 1
tmp = water//l
if water % l != 0:
tmp += 1
# a부터 판자 tmp 개 깔았으니까
end = a + (l * tmp) - 1
count += tmp
print(count)👍 제출
