[백준] 1449번 - 수리공 항승

문제 링크 : www.acmicpc.net/problem/1449

1449번: 수리공 항승

 

① 처음 테이프 시작 지점(start)을 (처음 물이 새는 위치 - 0.5), 마지막 지점(end)을 (처음 물이 새는 위치 + 0.5)로 설정 

② 물이 새는 위치를 하나씩 가져오면서 마지막 지점을 (현재 물이 새는 위치 + 0.5)로 갱신하고, (end-start)값이 테이프의 길이보다 큰지 확인

③ 크면 이전 물이 새는 위치까지 막을 수 있다는 것이므로, 테이프 개수를 1 증가하고 테이프 시작 지점을 (현재 물이 새는 위치 - 0.5)로 갱신하고 동일한 과정을 반복

④ 마지막 (start-end)값이 테이프 길이와 같거나, 마지막 물이 새는 위치가 하나 남았을 때에도 막아야하므로 (end-start)이 1이상이면 테이프 개수 1 증가

 

처음 소스코드를 제출했을 때 맞게 작성한 것 같았는데 틀려서 살펴보니 정렬을 하지 않은 상태에서 진행했었다. 예제에서는 물이 새는 위치가 오름차순으로 입력되어 있어서 정렬을 안해도 될 것 같지만 문제를 살펴보면 내림차순 or 오름차순으로 입력한다는 부분이 없으므로 물이 새는 위치를 오름차순으로 정렬한 후 진행해야한다. 

import sys

N, L = map(int, sys.stdin.readline().split())

locations = list(map(int, sys.stdin.readline().split()))
locations.sort() # 위치가 오름차순 or 내림차순으로 입력된다는 조건이 없으므로

tape_count = 0
start = locations[0] - 0.5
end = locations[0] + 0.5
for loc in locations:
    end = loc + 0.5

    if (end - start) > L:
        tape_count += 1
        start = loc - 0.5

if (end - start) >= 1:
    tape_count += 1

print(tape_count)