[BOJ 1449, Python 3] 수리공 항승

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

1449번: 수리공 항승

 

 

풀이

구멍이 난 곳마다 테이프를 붙여주는데 이때 테이프의 마지막 길이를 변수로 정해둡니다.

이 값을 val이라고 하고, arr[i] + 0.5 <= val이면 테이프가 이미 해당 구멍을 막고 있으니 continue로 지나가고,

arr[i] + 0.5 > val이면 구멍을 막지 못했으니 테이프를 추가하여 val = arr[i] - 0.5 + l로 길이를 업데이트 해주면 됩니다.

 

예제는 정렬된 값이지만, 문제에서 정렬된 상태로 입력값이 주어진다고 나와있지 않아서 정렬을 했습니다.

 

 

코드

n, l = map(int, input().split())
arr = sorted([*map(int, input().split())])
 
ans = 1
val = arr[0] - 0.5 + l
for i in range(1, n):
    if val >= arr[i] + 0.5: continue
    ans += 1
    val = arr[i] - 0.5 + l
 
print(ans)