[백준/Python] 1449번. 수리공 항승

📌 문제유형: 탐욕법(그리디) 

📌 문제링크 

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

 

📌 풀이코드 

N, L = map(int, input().split())
holes = list(map(int, input().split()))
covered = [0 for _ in range(len(holes))]
holes.sort()

count = 0
for i, h in enumerate(holes):
    able = [(h-0.5), (h-0.5) + L] # 커버 가능한 범위
    if not covered[i]:
        covered[i] = 1
        count += 1
        for j in range(i+1, len(holes)):
            if able[0] < holes[j] < able[1]:
                covered[j] = 1
    else:
        continue

print(count)

- 좌우 간격 0.5씩은 남겨둬야 한다고 했으니까, 특정 구멍 위치에 대해서 커버 가능한 범위를 찾고 싶었다.

- 그래서 현재 구멍에 대해 가능 범위를 미리 잡고, (able)

- 현재 구멍이 not covered 라면 그 다음 구멍 위치들에 대해 해당 able로 커버 가능한지도 살펴본다. 그러면 테이프 개수를 최소화할 수 있다.