BOJ 1477번: 휴게소 세우기

 

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

1477번: 휴게소 세우기

예제를 손으로 풀어봤지만,, 아직도 왜 70이 나오는 지 모르겠다,,,ㅋㅋㅋ

코드로 짜서 풀면 70이 나오긴 하는데 말이지,,

휴게소가 없는 구간의 최댓값을 low = 1 , high = L 로 두고 이분탐색을 통해 값을 찾아갔다. 두 지점 사이의 간격이 mid보다 크면 그 사이에 휴게소를 mid보다 작게 될 만큼 세워주고 m에 개수를 더해준다. 

그리고 m이 M보다 같거나 작다면 길이가 더 짧아질 수 있다는 것이므로 high = mid - 1을 해주고 ans를 최솟값으로 갱신한다. 이때 나는 m==M인 경우에만 갱신을 해야 한다고 생각했는데

"구하려고 하는 값이 휴게소들 사이의 거리의 최대값 중 최소값이고,

count가 M보다 작은 경우에도 역시 남는 휴게소들(count-M개)은 거리가 최대가 아닌 다른 곳에 아무렇게나 넣어도 최대값 mid는 유지가 될 수 있어서,

꼭 count==M인 경우에만 ans를 넣으면 틀린 답이 나올 수 있는 것 같아요." 라는 답이 질문에 있더라....

그리고도 계속 틀렸습니다 나와서 멘붕하고 있던 찰나 다시 코드를 살펴보니 ans를 구해놓고 정작 출력은 mid로 하고 있었다는,,,,,ㅎㅎ,,

import sys
from collections import deque
input = sys.stdin.readline
N, M, L = map(int, input().split())
loc = list(map(int, input().split()))
loc = [0] + loc + [L]
loc.sort()
low = 1
high = L
ans = L
while (low <= high):
    mid = (low+high)//2
    m = 0
    for i in range(1,N+2):
        if (loc[i] - loc[i-1] > mid):
            m += (loc[i]-loc[i-1]-1)//mid
    if (m <= M):
        high = mid - 1
        ans = min(ans, mid)
    else:
        low = mid + 1
print(ans)