[BOJ/python]1477번 휴게소 세우기

백준 1477번 휴게소 세우기 파이썬

문제 링크 - https://www.acmicpc.net/problem/1477

1477번: 휴게소 세우기

 

프로그래머스의 징검다리와 유사한 문제였다. - https://school.programmers.co.kr/learn/courses/30/lessons/43236

프로그래머스

 

만약 완전탐색으로 이 문제를 푼다면 휴게소를 설치할 수 있는 좌표의 조합을 모두 구해서 최댓값의 최소를 갱신하면 된다. 이러한 방식은 시간 복잡도가 매우 크기 때문에 최댓값의 최소를 한 번에 구하려고 하지 않고 단계적으로 찾아 나간다는 점을 유지하며 시간을 줄일 수 있는 방법을 찾고자 했다.

 

만약 세우려는 휴게소의 개수에 제한이 없다면 모든 위치에 휴게소를 세우면 된다. 이 경우에 최댓값의 최소는 1이 된다. 만약 세우려는 휴게소의 개수가 0개라면 현재 구간 중 최댓값이 최소가 되는 것이다. 즉, 최댓값의 최소는 세우려는 휴게소의 개수에 따라 바뀔 수 있다.

 

만약 임의의 구간 X가 최댓값이라면 X보다 큰 구간은 모두 휴게소를 설치하여 분할하면 된다. 분할할 때에는 절반을 자를 수도 있겠지만 구간의 길이 D를 [X, D-X]로 분할하면 분할된 두 구간 중 적어도 하나는 반드시 X보다 작거나 같기 때문에 분할의 횟수를 줄일 수 있다.

---

정리하자면, 최댓값이 X일 때, 휴게소를 얼마나 설치해야 하는 지 개수를 구한다. 다시 이 개수를 이용해 X의 범위를 수정하며 최댓값을 구하면 된다. 설치할 수 있는 휴게소가 남았다는 것은 최댓값의 범위를 줄일 수 있다는 뜻이다.

1. 풀이

• 모든 구간을 탐색하며 최댓값(mid)보다 큰 구간이 있다면 [mid, 구간의 길이-mid]으로 자르고 count+1을 한다.
• 구간의 길이- mid는 mid보다 클 수도 있으므로 tmp에 넣고 다시 확인한다.
• tmp 큐에 저장된 구간을 다시 확인하며 최댓값보다 큰 구간이 있다면 분할을 반복한다.
• 만약 현재 mid가 최댓값이 되기 위해 설치한 휴게소의 개수가 M보다 크다면 mid는 더 커야 한다. (덜 잘라야 한다.)
• 만약 현재 mid가 최댓값이 되기 위해 설치한 휴게소의 개수가 M보다 같거나 작다면 mid를 더 줄여도 된다. (더 자를 수 있다.)

2. 코드

from collections import deque

N, M, L = map(int, input().split())
G = list(map(int, input().split()))
G.append(0)
G.append(L)
G.sort()

D=[]
s,e=-1,-1
for i in range(1,N+2):
    dist = G[i]-G[i-1]
    D.append(dist)
    e = max(dist+1, e)
D.sort(reverse=True)

def check(maxLength):
    count = 0
    tmp = deque()
    # rest = -(maxLength-1)
    for dist in D:
        if dist>maxLength:
            count+=1
            tmp.append(dist-maxLength)
        else:
            break
    
    while tmp :
        dist = tmp.popleft()
        if dist>maxLength:
            count+=1
            tmp.append(dist-maxLength)

        if count>M :
            return count
        
    return count

answer = 0
while e-s>1:
    mid = (e+s)//2
    count = check(mid)
    if count <= M :
        e = mid
        answer = mid
    
    else : 
        s = mid
        
print(answer)

+) 큐를 사용하지 않고 구간의 거리가 mid 보다 크다면 mid로 나눈 몫을 count에 더해주는 방식으로 시간을 줄일 수도 있다.