[Python] 17266. 어두운 굴다리

문제

인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙빙 돌아서 집으로 간다. 안타깝게 여긴 인식이는 굴다리 모든 길 0~N을 밝히게 가로등을 설치해 달라고 인천광역시에 민원을 넣었다. 인천광역시에서 가로등을 설치할 개수 M과 각 가로등의 위치 x들의 결정을 끝냈다. 그리고 각 가로등은 높이만큼 주위를 비출 수 있다. 하지만 갑자기 예산이 부족해진 인천광역시는 가로등의 높이가 높을수록 가격이 비싸지기 때문에 최소한의 높이로 굴다리 모든 길 0~N을 밝히고자 한다. 최소한의 예산이 들 높이를 구하자. 단 가로등은 모두 높이가 같아야 하고, 정수이다.

---

첫 번째 줄에 굴다리의 길이 N 이 주어진다. (1 ≤ N ≤ 100,000)

두 번째 줄에 가로등의 개수 M 이 주어진다. (1 ≤ M ≤ N)

다음 줄에 M 개의 설치할 수 있는 가로등의 위치 x 가 주어진다. (0 ≤ x ≤ N)

가로등의 위치 x는 오름차순으로 입력받으며 가로등의 위치는 중복되지 않으며, 정수이다.

 

 

풀이

가로등 높이는 가로등 사이의 간격 중 제일 넓은 간격을 비출 수 있어야 한다. 굴다리 양쪽 끝과 가로등 사이의 거리는 그대로, 가로등과 가로등 사이의 거리는 /2한 뒤 반올림한 값으로 비교한다. 일단 한 번에 입력값을 다 받은 뒤, 반복문을 통해 처리하였다.

첫 번째 코드

import sys
import math

s = list(map(int, sys.stdin.read().split()))
X = s[2:]
start = 0
max = 0
for x in X:
    if start == 0:
        tmp = x
    else:
        tmp = math.ceil((x - start) / 2)
    start = x
    if tmp > max:
        max = tmp
if (s[0] - X[-1]) > max:
    max = s[0] - X[-1]
print(max if max != 0 else s[0])

 

잘 구현된 것 같지만 코드 효율성 측면에서 좀 더 개선할 수 있는 부분을 찾아보고 수정하였다.

 

1. math.ceil() 대신 정수 나눗셈 // 사용 

: import math를 하여 math.ceil(a)로 올림하는 대신 정수 나눗셈을 사용하여 (a+1)//2 로 대신하였다. import math를 하지 않고 실수 계산도 하지 않아 실행 시간 측면에서 개선되었다.

 

2. 양 끝 거리 계산을 한 번에 처리

: 기존엔 양 끝 가로등 거리 계산을 개별 if문을 사용하여 처리하였지만, max()를 사용하여 아예 for문 전에 한 줄로 계산을 마치고, for문 내에선 양 끝 거리를 뺀 구역만 계산하도록 하였다.

 

최종 코드

import sys

s = list(map(int, sys.stdin.read().split()))
X = s[2:]
start = X[0]
ans = max(X[0], s[0] - X[-1])
for i in range(1, len(X)):
    tmp = (X[i] - start + 1) // 2
    if tmp > ans:
        ans = tmp
    start = X[i]
print(ans)

훨씬 간결해졌고, 실행 시간과 코드 길이 모두 개선되었다. 

단순히 돌아가는 코드를 구현했다고 끝이 아니라 더 효율적으로 개선할 수 있을지 계속해서 고민하는 게 중요한 것 같다.

배운 것

• math.ceil(a): a를 올림한다.
• (a+1)//2: 정수 연산으로 a를 올림한 것과 똑같은 결과를 낸다.