[Baekjoon][Python] 1449번 수리공 항승

1449번 수리공 항승

문제

풀이

물이 새는 곳은 막는 문제이다. 지금 생각해보면 간단한 문제인데, 생각보다 문제를 이해하는데 오래 걸려 헤맸다.

문제의 조건을 하나하나 살펴보자.

1. 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다.
2. 길이가 L인 테이프를 무한개 가진다.
3. 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다.
4. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다.

1번 조건 때문에, 3번의 조건은 크게 의미가 없어졌지만, 코드에는 반영을 하였다.
2, 4번 조건에 맞게 생각을 해보면, 물이 새는 곳의 위치를 정렬 한 뒤 반복문을 돌며
마지막으로 테이프를 붙인 위치가 물이 새는 위치보다 작다면, 테이프를 붙이고 테이프를 자를 수 없으므로, 현재 위치 - 0.5 + 테이프 길이 만큼 더한 값이 다시 테이프를 붙인 최종위치가 된다.

이를 구현한 코드는 다음과 같다.(물이 새는 곳이 정수값으로만 존재하기 때문에 좌 우 0.5는 큰 의미가 없다)

import sys

def getTapeCount(leaks, n, l):
    lastTapeLoc = 0
    count = 0
    for i in range(n):
        if leaks[i] > lastTapeLoc:
            lastTapeLoc = leaks[i] - 0.5 + l
            count += 1
    return count

N, L = map(int, sys.stdin.readline().split())

locations = list(map(int, sys.stdin.readline().split()))
locations.sort()

print(getTapeCount(locations, N, L))

결론

이 문제는 해석이 어려웠을 뿐, 해석을 한 뒤에는 풀이가 매우 쉬웠다. 정렬이 가장 핵심인 문제였고, 그 이후엔 간단한 아이디어 만으로 풀리는 문제였다.