[Greedy] 1449번 - 수리공 항승(49일차)

#코드 실행 시간 단축
import sys
input = sys.stdin.readline

#구멍 개수, 테이프 길이 입력
N, L = map(int, input().split())

#구멍난 위치 입력받고 정렬
water = list(map(int, input().split()))
water.sort()

#테이프의 끝 위치 저장 변수
tape = 0.5
#사용된 테이프의 개수 변수
tape_cnt = 0

#모든 구멍에 대해
for i in range(N):
    #테이프를 붙일 필요가 없는 경우 (테이프의 끝이 해당 구멍을 덮지 못함)
    if(tape >= water[i]+0.5):
        #테이프 사용x
        pass
    #테이프를 붙여야 하는 경우 (테이프의 끝이 해당 구멍을 덮음)
    else:
        #해당 구멍을 시작으로 테이프를 붙이고, 테이프 위치 업데이트
        tape = water[i] - 0.5 + L
        #사용된 테이프 개수 추가
        tape_cnt += 1
#출력
print(tape_cnt)

#인사이트
#로직은 금방 떠올릴 수 있었다
#하지만 입력값이 정렬되어서 들어온다는 말이 없었기에 예제처럼 정렬 상태로 가정하고 풀어 오답
#솔직히 문제 독해만으로는 알 수 없는 정보라 출제자의 잘못이라고 보기는 하는데..어쩔 수 없다