[백준 1449번] 수리공 항승 - 파이썬

 

문제 링크:

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

1449번: 수리공 항승

---

 

문제 이해:

이 문제는 항승이가 물이 새는 곳의 위치를 찾아 테이프를 붙여 수리할 때, 필요한 테이프의 개수를 구하는 문제이다.

다음은 문제의 조건을 정리한 것이다.

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

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

 

문제를 이해해보자. 이해를 돕기 위해 단위 m을 사용한다.

만약 테이프의 길이가 2m라고 하고, 파이프에서 물이 새는 곳의 위치가 [1m, 2m, 100m, 101m]이라고 하자.

 

맨 처음 1m의 위치에서 물이 새기 때문에 문제의 조건 1)대로 0.5m ~ 1.5m를 테이프로 막아야 수리가 완료된다.

그다음 2의 위치에서는 1.5m ~ 2.5m를 테이프로 막아야 수리가 완료된다.

테이프의 길이가 2m이므로 1m, 2m 위치(0.5m~2.5m)에 테이프 1개로만 수리가 가능하다. 

 

다음으로 100m에서 물이 새는 곳의 위치를 살펴보자.

문제의 조건 1)대로 100m에서는 99.5m~100.5m를, 101m에서는 100.5m ~ 101.5m를 테이프로 막아야 수리가 완료된다.

테이프의 길이가 2m이기 때문에 100m, 101m(99.5m~101.5m) 위치에 테이프 1개로만 수리가 가능하다.

 

따라서 항승이가 필요한 테이프의 개수는 총 2개이다. (1,2m 위치에서 1개 + 100,101m 위치에서 1개) 

 

풀이 과정:

1. 파이프에서 물이 새는 곳의 위치를 오름차순 정렬한다.

2. 테이프를 붙이는 시작 지점 변수 start와 필요한 테이프의 개수 변수 count를 생성한다. 

3. 테이프를 붙일 수 있는 범위 내에 물이 새는 곳의 위치가 있다면 기존의 테이프로 붙인다.

3-2. 테이프를 붙일 수 있는 범위 내에 물이 새는 곳의 위치가 없다면 새 테이프를 붙이고 테이프 개수를 추가한다.

 

풀이 코드:

# 1449번 수리공 항승

# 입력값 받기
n, l = map(int, input().split())
data = list(map(int, input().split()))

# 물이 새는 위치 오름차순 정렬
data.sort()

# 테이프를 처음 붙이는 시작지점
start = data[0]
# 필요한 테이프의 개수
count = 1

# 물이 새는 곳의 위치를 차례대로 받으면서
for location in data[1:]:
  # 테이프를 붙이는 범위 내에 물이 새는 곳의 위치가 있다면
  if location in range(start, start+l):
    # 기존 테이프 사용
    continue
  # 기존의 테이프로 붙이지 못한다면
  else:
    # 새 테이프를 사용하고 테이프 개수 추가
    start = location
    count += 1

# 필요한 테이프의 개수 출력
print(count)

 

백준 1449번 수리공 항승