[백준] 1449 수리공 항승

문제

• 왼쪽에서 X 만큼 떨어진 거리에서 물이 샐 때, 그 위치의 좌우 0.5 만큼 간격으로 테이프로 막아야 한다.
• 물이 새는 위치와 길이가 L인 테이프를 무한개 가지고 있고 물 새는 곳이 N개 일 때, 필요한 최소 테이프의 개수는?
  • 1 <= L, N <= 1000
• 테이프는 자를 수 없고, 테이프를 겹쳐 붙이는 것은 가능하다. 

 

풀이

• 물 새는 곳의 위치를 정렬하고, 처음부터 차례로 테이프를 붙이기 시작
• 테이프 길이 L에 포함되는 연속된 위치인 경우 넘어가기

 

N, L = map(int, input().split())
loc = list(map(int, input().split()))
loc.sort()      # 물 새는 곳 위치 정렬

tape = set()    # 테이프 붙여진 위치
answer = 0      # 테이프 개수
for x in loc:
    if x in tape :  # 이미 테이프 붙여진 경우 넘어가기
        continue
    answer += 1     # 거리 L만큼 테이프 붙이기
    for i in range(x, x+L):
        tape.add(i)

print(answer)

 

References

• 백준 1449
• 2023.05.02 오늘의 문제