백준 GOLD 4 [1477번] 휴게소 세우기 [반례 포함] {언어 : Python}

문제 링크

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

1477번: 휴게소 세우기

정답 코드

import sys
input = sys.stdin.readline

# N 현재 휴게소 개수
# M 더 지으려고 하는 휴게소 개수
# L 고속도로의 길이
N, M, L = map(int, input().split())
if N == 0:
    if L % (M+1):
        print(L//(M+1)+1)
    else:
        print(L//(M+1))
else:
    restAreas = sorted(list(map(int, input().split())))
    distances = [restAreas[0]-0]
    for idx in range(1, N):
        distances.append(restAreas[idx]-restAreas[idx-1])
    distances.append(L - restAreas.pop())
    distances.sort()

    left = 1
    right = L - 1
    while left <= right:
        searchD = (left + right) // 2
        maxD = 0
        cnt = 0
        for d in distances:
            if d > searchD:
                cnt += (d - 1) // searchD
        if cnt > M:
            left = searchD + 1
        else:
            right = searchD - 1
    print(left)

풀이 방법

1. N이 0일 때와 아닐 때를 비교해서 결과를 도출했다.
   1. 0일때는 결국 더 지으려고 하는 휴게소의 개수와 고속도로의 길이만 필요하다.
   2. 이 부분에서 많이 틀릴 것 같다.
2. 시작점부터 도착점 까지의 휴게소간 거리를 리스트로 만들었다.
   1. 첫번째 인덱스의 휴게소 위치랑 출발점 위치를 뺄 때는 인덱싱을 사용했다.
      1. restAreas[0] - 0
   2. 하지만 맨 마지막 휴게소 위치를 찾을 때는 그냥 pop을 사용했다.
      1. L - restAreas.pop()
      2. 왜냐하면 마지막 인덱스 까지 인덱싱하는데 걸리는 시간보다 pop을 통해 빼주는 시간이 더 빠르기 때문이다.
3. 이분 탐색을 실행하는데
   1. left는 1이고 right는 L - 1이다.
      1. M의 값이 최소 하나 이상이고 바로 옆에 휴게소를 짓는다고 해도 1 차이 나기 때문에 left = 1
      2. 위와 논리는 동일하다.
   2. 만들어둔 distances(거리 배열)를 통해 찾으려고 하는 값(searchD)보다 큰 겨우만 cnt에 값을 더해준다.
   3. cnt 값이 휴게소를 지을 개수보다 많으면 값이 작다는 의미이므로 left의 값을 키워 범위를 좁힌다.
   4. cnt 값이 M 보다 작거나 같으면 범위의 크기가 더 크다는 말이므로 right값을 줄여서 범위를 좁힌다.
4. 마지막으로 이중탐색이 종료되면 결국 찾으려고 하는 값은 left나 right나 (left+right)//2 나 같기 때문에 그냥 습관처럼 left를 return 한다.
   1. 하지만 이 방식에 대해서도 분명히 반례가 존재하는 코딩테스트 문제가 있을 수 있으니 주의한다.

반례

	반례 1	반례 2
input	0 10 333	0 9 300
output	31	30

느낀점

• 풀고 나서 떠오른건데 반올림이 아니라 올림을 하면 되는 것을 굳이 d에서 1을 빼고 L을 M으로 나눈게 나머지가 있는지 없는지를 확인했다.
• 하지만 왜인지 모르겠으나 원본 코드가 조금 더 빨랐다. 4~8ms정도

# 원본 코드 1
if N == 0:
    if L % (M+1):
        print(L//(M+1)+1)
    else:
        print(L//(M+1))

# 수정된 코드 1
import math
if N == 0:
    print(math.ceil(L/(M+1)))