[Python] 백준 17266번 - 어두운 굴다리

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

 

나의 답

import math

l = int(input())
cnt = int(input())
spot = list(map(int, input().split()))

gap = max(spot[0],l-spot[-1])

for i in range (0,cnt-1):
    gap = max(gap,math.ceil((spot[i+1]-spot[i])/2))

print(gap)

 

가로등의 높이를 구해보았다.

 

처음 설치된 가로등은 0으로부터 몇 떨어져있느냐가 관건이고,

마지막으로 설치된 가로등은 맨끝(l)으로 부터 몇 떨어져있느냐가 관건이기 때문에

 

둘 중에 큰 값을 gap 값으로 설정하였다.

큰 값으로 설정한 이유는 둘 다 동시에 만족시켜야 가로등이 처음, 끝을 모두 비출 수 있기 때문이다.

 

그 다음, 처음 가로등 끝 가로등 사이에 있는 가로등끼리는

반씩만 나눠서 비춰지더라도, 모두 비출 수 있기 때문에 각 사이의 거리를 2로 나눠서 큰 값을 구하도록 했다.

 

그렇게 gap 출력했더니 성공 .  ..

 

다른 사람 풀이 (이분탐색 버전) - https://jinho-study.tistory.com/956 참

def bs(li, m):
    if li[1]-li[0] > m:
        return 0
    if li[-1]-li[-2] > m:
        return 0
    for i in range(1, len(li)-2):
        if (li[i+1]-li[i])/2 > m:
            return 0
    return 1

N, M = int(input()), int(input())
li = [0] + list(map(int, input().split())) + [N]
s, e = 0, N
res = 0
while s <= e:
    m = (s+e)//2
    if bs(li, m):
        e = m-1
        res = m
    else:
        s = m+1
print(res)

 

와 이렇게도 풀 수가 있군.........

이분 탐색 너무 헷갈린다... 퀵소트

 

근데 ! 이 문제는 처음 방법으로 푸는 게 더 빠른 듯 하다.

 

Kotlin버전 답

import java.util.*
import kotlin.math.ceil
import kotlin.math.max

fun main() {
    val scanner = Scanner(System.`in`)
    val l = scanner.nextInt()
    val cnt = scanner.nextInt()
    val spot = IntArray(cnt) { scanner.nextInt() }.sorted()

    var gap = max(spot[0], l - spot[cnt - 1])

    for (i in 0 until cnt - 1) {
        gap = max(gap, ceil((spot[i + 1] - spot[i]) / 2.0).toInt())
    }

    println(gap)
}

 

알게된 점

Python에서 반올림은 round 함수 쓰면 다 되는 줄 알았는데 아니었다..

3.5 인경우 3이 홀수여서 4가 되는데,

4.5 인경우는 4가 짝수여서 그냥 4가 된단다. 

 

그래서 math.ceil을 이용해서 올림 함수를 썼어야 했따....

 

이건 백준 광고에 뜨길래 ... 🍀🍀🍀🍀