[Python] 백준/BOJ - 1449번: 수리공 항승

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

1449번: 수리공 항승

 

문제

항승이는 파이프 회사의 수리공이고, 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다.

파이프에서 물이 새는 곳은 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다.

항승이는 길이가 L인 테이프를 무한개 가지고 있다. 항승이는 테이프를 이용해 물을 막으려고 한다. 항승이는 물을 막을 때 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다.

물이 새는 곳의 위치와 항승이의 테이프 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프는 자를 수 없고, 겹쳐서 붙이는 것은 가능하다.

 

입력

첫째 줄에 물이 새는 곳의 개수 N, 테이프의 길이 L이 주어진다.

둘째 줄에는 물이 새는 곳의 위치가 주어진다.

(1 <= N, L, 물이 새는 곳의 위치  <= 1,000)

 

출력

항승이가 필요한 테이프의 개수

 

예제 입력 1

4 2
1 2 100 101

 

예제 출력 1

2

 

풀이

n, l = map(int, input().split())
s = list(map(int, input().split()))
s.sort()

start = s[0]
end = s[0] + l
cnt = 1

for i in range(n):
    if start <= s[i] < end:
        continue
    else:
        start = s[i]
        end = s[i] + l
        cnt += 1
        
print(cnt)

 

먼저 N과 L, 물이 새는 곳의 위치들을 입력받는다. 그리고 물이 새는 곳이 연속하는 경우를 따져주기 위해서 물이 새는 곳의 리스트인 s를 sort해준다. (s의 순서는 바뀌어도 상관이 없다!)

start를 s의 0번째 요소로 지정해주고, end를 s[0]에 길이 L을 더한 값으로 해준다. 이는 s[0]부터 s[0]+L의 전까지는 길이 L의 테이프로 막을 수 있다는 것을 의미한다.

 

예를 들어 s가 [ 1, 2, 3 ] 이고 L이 2인 경우 s[0] = 1, s[0] + l = 3이다. 문제에서 좌우로 0.5씩은 막아줘야 한다고 했기 때문에 1부터 길이 2만큼 막으려면 0.5부터 2.5까지 막을 수 있다. 따라서 s[0]부터 L만큼 막을 수 있는 범위는 s[0] <= 물이 새는 곳 < s[0] + l 이 되는 것이다.

 

이 원리를 이용해 n만큼 for문을 돌려주면 s[i]가 start보다 크거나 같고, end보다 작으면 start에서부터 붙인 테이프로 현재 지점을 막을 수 있다는 의미이므로, continue해준다.

그렇지 않은 경우, start부터 붙인 테이프로 막을 수 없다는 의미이기 때문에 start 지점을 옮겨줘야 한다. start를 현재 값 s[i]로 지정해준 뒤, end값을 s[i] + l로 지정해준다. 테이프를 새로 하나 붙였기 때문에 cnt도 +1해주면 된다.