[파이썬] BOJ_1449(수리공 항승)

문제

 

www.acmicpc.net/problem/1449

1449번: 수리공 항승

---

 

해설

 

물이 새는 곳을 막기 위해서는 앞뒤로 총 1만큼의 간격이 더 필요하다.

시작위치보다 물 새는 위치가 더 뒤에 있을 때 막을 수 있다.

 

일단 구멍 하나를 막으면,

테이프 길이 - 1(앞뒤 0.5) 위치에 있는 구멍까지 다 막을 수 있다.

 

그렇기 때문에 시작 위치만 마지막으로 막은 구멍으로 옮겨주면 간단하게 해결할 수 있다.

---

코드

 

-파이썬

#백준 1449(수리공 항승)

n, l = map(int, input().split())  #물이 새는 곳 개수, 테이프 길이
leak = list(map(int, input().split()))  #물 새는 위치

leak.sort()
start = 0
res = 0

for i in leak:
    if start < i:
        res += 1
        start = i + l - 1

print(res)