[백준] 1449 수리공 항승 (Python 파이썬)

www.acmicpc.net/problem/1449

1449번: 수리공 항승

문제 설명

수리공이 물이 새는 파이프를 테이프로 수리한다. 테이프는 무한 개 갖고 있으며, 최소한의 테이프를 사용하여 수리해야 한다. 물이 새는곳을 막을 때, 그 위치의 좌우로 0.5만큼씩을 더 막아줘야 물이 새지 않는다. 테이프는 자를 수 없으며, 겹칠수는 있다. 또, 물이 새는 곳의 위치는 자연수이다.

---

풀이 과정

최소한의 개수로 최대의 이익을 취해야 하는 그리디 알고리즘 문제이다.

 

먼저 테이프의 길이가 1이면, 테이프 1개로 지점을 1개만 막을 수 있다. 그래서 n개의 테이프를 사용해야 한다.

 

그 외의 경우에는, 테이프를 막는 첫 위치는 첫 지점에서 테이프길이의 절반만큼 더한구간이 되는데, 0.5이전도 막아주어야 하므로 0.5를 빼준 곳이 된다. 그래야 이 위치가 첫구간을 막으면서 첫구간과 가장 멀리 떨어진 곳이 되기 때문이다.

 

막은 위치를 현재 테이프의 위치로 지정을 해 주고, 현재 테이프가 커버할 수 있는 구간까지는 테이프를 더 붙일 필요가 없다. 

 

하지만, 현재 테이프가 커버할 수 있는 구간을 벗어나게 되면 새로 테이프를 붙여주어야 하는데,

(다음 물이새는 위치+0.5)가 (현재 테이프가 있는 곳+테이프 길이의 절반) 보다 클 경우에는 새로 테이프를 붙여주어야 하므로, 테이프의 위치를 (다음 물이새는 위치 + 테이프 길이 절반 - 0.5)로 이동시켜야 한다.

 

이렇게 하면, 최소한의 테이프로 수리를 하게 된다.

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

if l == 1:
    print(n)

else:
    cnt = 1
    cur = fix[0] + l/2 - 0.5

    for i in range(1, n):
        if cur+l/2 < fix[i]+0.5:
            cnt += 1
            cur = fix[i] + l/2 - 0.5
    print(cnt)

 

https://github.com/HongEunho

HongEunho - Overview

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !