[백준] 1449: 수리공 항승

문제: https://www.acmicpc.net/problem/1449

간단하게 풀릴줄 알았던 문제였는데 한가지를 간과하여 생각보다 오래걸린 문제이다.

---

문제해석

길다란 파이프가 있고 파이프 곳곳에는 구멍이 나있다. 또한 길이가 일정하고 자를 수 없는 테이프가 무한이 주어진다. 이 테이프를 가지고 파이프에 구멍난 곳을 수리해야한다. 구멍 난 곳에 테이프를 붙일 때는 좌우 최소 0.5 이상의 테이프 길이를 남겨 놔야한다. 파이프 수리에 필요한 테이프를 최소한으로 사용하는 개수를 구하시오.

---

해결방법

• 구멍이 있을 경우 테이프를 붙인다.
• 테이프를 붙일때 구멍을 커버 가능한 범위를 지정한다.
• 해결된 파이프의 구멍은 테이프를 붙이지 않는다.

---

코드 해석

구멍 위치를 입력받을때 정렬하여 배열에 지정한다. 정렬하는 이유는 작은 구멍부터 차례대로 테이프를 붙일 예정이기 때문이다.

이제 하나씩 구멍난 곳을 순회한다. 해당 구멍이 이전 테이프가 커버 되는 곳에 포함되어 있다면(해결된 구멍) 다음 구멍으로 넘어가고
만약 그렇지 않다면 테이프 개수를 하나 추가하고 테이프를 붙인다.

이때 테이프 시작 위치는 원래 구멍의 위치에서 0.5 만큼 띄어야하지만 우리는 코드상 테이프 시작 위치가 아닌 테이프가 구멍을 커버 가능한 범위를 구현할 것이기 때문에 구멍 커버를 시작하는 위치인 구멍 위치를 시작 위치로 설정했다. 이는 우리가 이 후에 나올 구멍들을 최대한 커버하기 위해 시작 위치는 최소한으로 설정한 것이다. 이 부분을 인지 하지 못하여 계속 해매었다.

테이프가 커버가능한 마지막 위치는 ℓ(테이프 길이) - 0.5(시작 위치 쪽 공백) + 0.5(끝 위치 쪽 공백) 이다. 마찬가지로 이것은 이후에 나올 구멍들을 최대한 커버하기 위해 마지막 위치를 최대로 설정한 것이다.

테이프의 커버 가능한 위치를 정리하자면 아래 그림과 같다.

이제 처음부터 끝까지 파이프 구멍을 순회하면서 구멍이 테이프가 커버하는 범위에 포함 되어 있다면 다음 구멍으로 넘어가고 그렇지 않다면 새로운 테이프를 붙이고 새로운 테이프 커버 범위를 지정한다.

---

코드

import sys
input = sys.stdin.readline

n, l = map(int, input().strip().split())
#주어진 배열이 정렬됨을 확신 할 수 없어서 정렬
arr = sorted(list(map(int,input().strip().split())))

#테이프 시작, 끝, 개수 변수
start = 0
end = 0
cnt = 0
for i in range(n):
	#해당 구멍이 이전 테이프 범위에 포함되는 체크
	if start < arr[i] <= end:
		continue
	#포함되어 있지 않다면 테이프 부착
	cnt += 1
	start = arr[i]
	end = arr[i] + (l-1)
print(cnt)

---

테이프 커버 설정 범위 개념을 잘 인지했다면 금방 풀었을 수 도 있을 문제 였던 것 같다.