[백준 - Python] 1449. 수리공 항승 (그리디)

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

1449번: 수리공 항승

 

코드

import sys
n, tapeLen = map(int, input().split())
pos = list(map(int, sys.stdin.readline().split()))
pos.sort()

start = pos[0] - 0.5
end = start + tapeLen
cnt = 1

for i in range(0, len(pos)):
    if start < pos[i] < end:
        continue
    else:
        cnt += 1
        start = pos[i] - 0.5
        end = start + tapeLen

print(cnt)

 

문제에서 무엇을 해결해야 하는지에 대한 이해는 되었지만,

접근을 잘못해서 간단하게 풀 수 있는 문제를 복잡하게 풀기 시작했고, 해결도 못했다.

 

연달아 새는 곳은 테이프 하나로 이어서 막을 수 있겠구나 라는 생각에서 시작해서

'연달아 새는 지점들'에 너무 집중한 나머지 쉬운 접근법 생각을 못한 것 같다.

 

연달아 새는 길이를 리스트에 시작 지점이랑 튜플로 묶어서 저장하고,

연달아 새는 지점의 길이가 테이프 길이보다 작을 때, 클 때 비교하고

생 난리를 쳤는데 ㅎㅎ;;

(너무 난잡해진다 싶으면 다른 아이디어를 생각해보자 !)

 

 

그냥 시작점과 테이프 길이를 고려한 끝점 변수를 이용해서

새는 지점이 시작점 끝점 범위 내에 있으면, 현재 테이프로 수리가 가능한 것이고

범위 밖에 있으면, 새로운 테이프를 쓰는 아이디어로 접근하면 쉽게 풀릴 수 있는 문제였다.

 

새는 지점의 물을 막기 위해서는

적어도 그 위치의 좌우 0.5만큼의 간격을 줘야 물이 새지 않으며,

왼쪽에서 정수만큼 떨어진 거리만 물이 샌다고 문제에서 주어졌다.

 

따라서 시작점은 0.5를 빼주고

끝 점은 시작점에 테이프 길이를 더해주어 범위를 설정하는 것만으로

pos[i]를 막을 수 있는지 없는지 알 수 있다.