(Python) - BOJ(1449번) : 수리공 항승

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

1449번: 수리공 항승

---

• 해설 : 

수리공 항승은 물이 새는 파이프를 테이프로 막으려고 한다. 테이프의 길이 L과 막아야 할 구멍의 개수 N이 주어지고

막아야할 구멍의 위치가 주어질 때, 테이프를 최대한 적게 사용하여 모든 구멍을 막는 경우를 찾는 문제이다.

 

 

 

---

• 풀이 :

그리디하게 해결할 수 있다. 구멍이 있는 위치를 만났다면, 이 때 최대한 많은 구멍을 막게끔 구현하면 되는 것이다.

핵심은 막은 첫 번째 구멍의 위치와 다음 막을 구멍 사이의 거리 + 1 보다 테이프가 긴지 짧은지에 대한 확인이다.

 

 

---

• 소스코드 : 

 

N , L = input().split()
N = int(N)
L = int(L)
m = list(map(int,input().split()))
cnt = 0
i = 0
j = 0
m.sort()
while i<len(m):
    while j != len(m) and (L-1) >= m[j]-m[i]:
        j+=1
    i=j
    cnt+=1
print(cnt)