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

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

레벨: 실버 3

언어: python

---

문제풀러가기

📑풀이 과정

물이 세는 곳 하나를 막기 위해서는 좌우 0.5 만큼이 필요하다

물이 세는 곳이 1이라면 0.5 ~ 1.5 구간이 테이프가 발리는 구간이다.

예시 처럼 테이프의 길이가 2이고
1 과 2 에서 물이 셀 때
0.5 ~ 2.5 까지 테이프를 붙여야하고 이때 길이 2짜리가 한개 들어간다.

1. 물이 세는 곳의 입력을 배열에 저장하고 오름차순으로 정렬한다.
2. 처음 들어오는 값을 기준으로
   테이프를 처음 붙이는 곳 arr[0] - 0.5 -> start라는 변수에 저장
   테이프가 끝나는 곳 start + L -> end라고 저장
3. arr 순회 하면서 start 보다 크고 end 보다 작은 값은 넘어가고 범위를 넘어가면 cnt를 1더하고 범위를 새로 설정한다.

📋풀이 코드

import sys

input = sys.stdin.readline

N , L = map(int, input().split())
arr = list(map(int, input().split(' ')))
arr.sort()

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

print(cnt)

---