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

 

n, l = map(int, input().split())

where = list(map(int, input().split()))
where.sort()

start = 0
cnt = 0
for loc in where:
    if start < loc: # 덮혀진 곳은 더 이상 탐색 필요 없음.
        start = loc + l - 1 # 하나의 테잎으로 끝나는 위치로 갱신해줌.
        cnt += 1

print(cnt)

 

코드 설명

수리해야 하는 곳의 위치를 순서대로 하기 위해 입력 받은 후 정렬을 해준다. 이미 끝난 위치를 기록하기 위한 start 변수를 선언하여 준다.

반복문을 돌면서 탐색 시작 위치 보다 수리하려는 위치가 클 경우에만 테잎을 붙히고, 시작 위치를 loc + 테잎의 길이 - 1 로 계속 갱신한다.

 

Point : 테잎으로 마무리 한 곳은 다시 덮을 필요가 없으므로 start 라는 변수를 통해 수리가 완료된 곳의 위치를 기록한다.

즉 수리가 완료된 곳은 테이프를 더 붙일 필요가 없는 것이다. 따라서 loc 값이 큰 경우에만 카운트를 해준다.

정렬과 위치를 저장함으로써 문제에 보다 쉽게 접근할 수 있다.