BAEKJOON #1449) 수리공 항승 (python)

알고리즘 분류: 그리디

 

1449번: 수리공 항승

💡 풀이

n, l = map(int, input().split())
loc = list(map(int, input().split()))
loc.sort()
cnt = 1
tmp = loc[0]

for i in range(n-1):
    if loc[i+1] <= tmp+l-1:
        continue
    else:
        cnt += 1
        tmp=loc[i+1]
print(cnt)

• 차례대로 테이프를 사용할 개수를 카운트하기 위해 물이 새는 위치를 오름차순으로 정렬한다.
• 사용되는 테이프의 개수를 카운트할 변수 cnt를 생성한다.
• 하나의 테이프를 붙여서 물을 새는 것을 막기 시작한 위치를 tmp에 할당한다. (처음에는 loc[0])
• 여기서 사용되는 규칙은 테이프의 길이가 L이면, tmp(물이 새는 위치)부터 tmp+L-1까지 테이프를 붙여서 물을 막을 수 있다.
• 따라서 for문으로 물이 새는 모든 위치를 돌면서 tmp+L-1보다 작거나 같은 위치는 같은 테이프를 사용해 한번에 막을 수 있다는 이야기이므로 cnt를 증가시키지 않고 반대의 경우만 cnt를 1씩 증가시키고, 그 위치부터 테이프는 다시 시작되므로 tmp를 그 위치로 다시 할당한다.