[baekjoon] 백준 1449번(파이썬): 수리공 항승

문제

1449번: 수리공 항승

- 항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다.

- 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다.

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

- 항승이는 길이가 L인 테이프를 무한개 가지고 있다.

- 항승이는 테이프를 이용해서 물을 막으려고 한다.

- 항승이는 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다.

- 물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어진다.

- 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것은 가능하다.

- 이때, 항승이가 필요한 테이프의 최소 개수를 구하는 문제이다.

- 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다.  N과 L은 1,000보다 작거나 같은 자연수이다.

- 물이 새는 곳의 위치는 1,000보다 작거나 같은 자연수이다.

알고리즘

- 물이 새는 곳의 개수와 테이프의 길이를 입력받는다.

- 물이 새는 곳의 위치를 입력받아 리스트 변수에 넣는다.

- 가까운 거리부터 수리하기 위해 물이 새는 곳의 위치를 오름차순으로 정렬한다.

- 반복문을 통해 물이 새는 곳의 위치를 확인한다.

- 수리를 한 위치와 물이 새는 곳의 위치를 비교한다.

- 수리를 한 위치가 물이 새는 곳의 위치보다 작으면 수리를 한다.

- 테이프 하나로 수리를 하고 물이 새는 곳부터 테이프 길이를 더해 수리한 위치를 바꾼다.

- 수리를 한 위치가 물이 새는 곳의 위치보다 크면 이미 물이 새는 곳은 수리했다고 판단하여 넘어간다.

- 테이프 사용 횟수를 출력한다. 

코드

import sys

n, l = map(int, sys.stdin.readline().split())
position = list(map(int, sys.stdin.readline().split()))
# 가까운 위치부터 수리하기위해 오름차순으로 정렬 한다.
position.sort()

# 수리를 한 위치
repair = 0
# 테이프 사용 횟수
cnt = 0

# 반복문을 통해 물이 새는 곳의 위치를 확인한다.
for i in position:
    # 수리를 한 위치와 물이 새는 곳의 위치 비교
    if repair < i:
        # 테이프 하나로 수리
        cnt += 1
        # 물이 새는 곳의 위치와 테이프 길이를 더해 수리를 한 위치를 바꿈
        # 물이 새는 곳부터 수리를 하기 때문에 -1을 해준다.
        repair = i + l - 1

print(cnt)

결과

코드를 분석하게 되면 수리를 한 위치와 물이 새는 곳의 위치를 비교하는데, 비교할 때 물이 새는 곳의 위치가 수리를 한 위치보다 크다면 수리를 하고 수리를 할 때 테이프의 길이만큼 물이 새는 곳의 위치 뒤에도 자동으로 수리가 되므로 물이 새는 곳의 위치에서 테이프의 길이를 더한 후 물이 새는 곳의 위치부터 테이프로 수리했기 때문에 1을 빼준 것을 확인할 수 있다. 그리고 물이 새는 곳의 위치가 수리를 한 위치보다 작다면 이미 이전에 물이 새던 곳에서 수리를 하다가 같이 수리가 되었다고 판단하고 넘어가면 된다.  

github

junjange/CodingTest