[Python 파이썬]백준 1477번 - 휴게소 세우기

2023년 5월 8일

문제 링크 : 1477번 - 휴게소 세우기

문제

다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다.

다솜이는 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 휴게소는 정수 위치에만 세울 수 있다.

다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한다. 다솜이는 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. (반드시 M개를 모두 지어야 한다.)

예를 들어, 고속도로의 길이가 1000이고, 현재 휴게소가 {200, 701, 800}에 있고, 휴게소를 1개 더 세우려고 한다고 해보자.

일단, 지금 이 고속도로를 타고 달릴 때, 휴게소가 없는 구간의 최댓값은 200~701구간인 501이다. 하지만, 새로운 휴게소를 451구간에 짓게 되면, 최대가 251이 되어서 최소가 된다.

입력

첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다.

출력

첫째 줄에 M개의 휴게소를 짓고 난 후에 휴게소가 없는 구간의 최댓값의 최솟값을 출력한다.

제한

• 0 ≤ N ≤ 50
• 1 ≤ M ≤ 100
• 100 ≤ L ≤ 1,000
• 1 ≤ 휴게소의 위치 ≤ L-1
• N+M < L
• 모든 휴게소의 위치는 중복되지 않음
• 입력으로 주어지는 모든 수는 정수

알고리즘 분류

• 이분 탐색
• 매개 변수 탐색

---

문제 접근

가장 먼저 접근했던 방법은 다음과 같고, 결론부터 말하자면 틀렸다.

1. 입력 값을 입력받음
2. 휴게소의 위치를 리스트로 입력받고, 고속도로 양 끝점 또한 입력받음
3. 특정 두 지점 간 거리가 가장 먼 경우를 찾고, 해당 두 지점의 가운데에 휴게소를 설치하여 사이 거리를 절반으로 나눈다.
4. 3의 과정을 M번 반복하여 M개의 휴게소를 추가로 짓고, 최종 지점들 간의 위치를 계산하여 가장 긴 간격을 출력한다

이 방법을 반복하면 오류를 범하게 된다. 다음과 같은 경우를 보자

<고속도로의 길이 : 500, 설치할 휴게소 개수 M : 2, 이미 존재하는 휴게소 위치 : 100>

위 1~4 순서대로 문제를 풀면 다음과 같은 결과가 도출된다.

<(1)에 휴게소를 비치한 이후, (2)에 휴게소를 비치하였음>

가장 긴 간격을 찾아 중간지점에 휴게소를 설치한 결과로, 각 지점 간 간격의 최댓값 (휴게소가 없는 최대 거리)은 200이 된다.

하지만 다음의 경우를 보자.

<휴게소 설치를 다음과 같이 진행하니 위의 경우보다 최대 거리가 더 짧아졌음>

문제가 바라는 바는 '각 지점 간 간격의 최댓값'으로 올 수 있는 여러 경우의 수 중, '최솟값'을 구하라는 것이다.

정확한 거리는 제대로 측정해보지 않았으나, 적어도 200보단 짧은 최댓값이 도출되었음을 알 수 있다.

그렇다면 어떻게 접근해야 할까? 이 문제는 이분 탐색이 핵심 알고리즘이다.

 

이분 탐색의 핵심은 시작점(start)과 끝점(end)의 초기값을 어떻게 세팅해야 하며, 양 끝점의 중간지점인 mid 값을 통해 무엇을 얻고 싶은지 알아야 하는 것이다.

적지 않은 시간동안 고민을 한 결과

1. 초기 start와 end를 "고속도로 전체의 양 끝점"으로 초기 세팅하고
2. 중간 지점인 (start + end) // 2 = mid 값을 "새로 설치할 휴게소 간 간격"으로 가정한 뒤,
3. 각 지점 사이에 휴게소를 간격 mid로 가정했을 때 각각 몇 개 설치할 수 있는지를 "합산" 하여
   1. "합산" 한 수가 목표로 설치하는 휴게소의 수 M보다 크다면 "합산"한 수를 줄이기 위해 mid 값을 키워야 하므로 start = mid + 1로 재선언
   2. "합산"한 수가 목표로 설치하는 휴게소의 수 M보다 작다면 "합산"한 수를 늘리기 위해 mid 값을 줄여야 하므로 end = mid - 1로 재선언
   3. "합산"한 수가 목표로 설치하는 휴게소의 수 M과 같다면 설치할 휴게소 간 간격을 "더 줄일 수 있는지 검사"하기 위해 end = mid - 1로 재선언.
4. 3-1과 3-2의 과정으로 각각 가정한 mid 값을 토대로 설치하는 휴게소의 수 M에 근접할 때까지 이분 탐색을 진행하다, 3-3에 도달한 이후, 거리를 더더욱 줄일 수 있을 때까지 3-3을 반복한다. 최종 end가 start보다 작아져 이분 탐색이 종료되는 시점에서 가장 최근 mid값이 이 문제가 바라는 "휴게소가 없는 구간의 최댓값의 최솟값"이다.

순서도

1. 입력 값을 입력받음

2. 설치할 휴게소 간 거리를 구하기 위한 이분탐색을 위해
	start = 1, end = L로 선언. mid = (start + end) // 2 로 선언하며, mid는 설치할 휴게소 간 거리 추정 값.

3. 각 구간의 거리에 mid 간격으로 휴게소를 설치할 때 몇 개를 설치할 수 있는지를 합산한다.
    3-1. 합산 값이 M보다 크면 너무 많이 설치할 수 있으므로 
    	이보다 더 적게 설치하기 위해 mid를 키워야 함 : start = mid + 1 으로 재선언
    3-2. 합산 값이 M보다 작으면 더 설치할 수 있으므로
    	이보다 더 많이 설치하기 위해 mid를 줄여야 함 : end = mid - 1으로 재선언
    3-3. 합산 값이 M과 같으면 간격의 길이를 더 최소화 할 수 있는지 검사하기 위해 mid를 줄여본다 : end = mid - 1

4. start가 end보다 커지는 순간, 이분탐색을 멈추며, 마무리는 항상 3-3 과정을 통해 거리를 조금씩 줄이다 끝나기 때문에
    탐색 종료 시점 가장 최근의 mid값이 곧 원하는 출력 값이다.

문제 접근에서는 초기 start를 고속도로의 시작점인 0으로 세팅한다고 했는데 왜 순서도에서는 1인가? 이는 밑에 주의할 점에서 자세히 풀도록 하겠다.

 

---

입력 예제

6 7 800
622 411 201 555 755 82

 

출력 예제

70

---

주의할 점

• 초기 start를 0으로 지정할 경우 다음과 같은 예제 입력에서 ZeroDivisonError를 유발하게 된다.

입력 : 0 99 100

출력 : 1

start = 0, end = 100으로 초기 세팅 후, mid값을 계속 줄여나가기 위해 end = mid - 1를 반복하다,

start = 0, end = 4까지 end 를 줄이게 된다. 여기서 mid는 2이고, mid가 2일 때에도 0~100 사이 휴게소는 49개만이 설치가 가능하기에 M보다 작으므로 mid를 줄이기 위해 end = mid - 1 = 1이 된다. 여기서 문제가 생긴다.

mid값은 0 + 1 // 2 = 0이 되고, 0~100 사이 휴게소를 몇개 지을 수 있는지 연산하는 부분에서, mid로 나누어야 하는데

0으로 나누는 경우가 생기기 때문에 ZeroDivisonError를 겪게 되는 것이다.

해결 방법으로는, start의 초기 세팅을 1로 해주면 된다. 위 경우도 마지막 mid 값이 1+1 // 2 = 1이 되고, 0~100 사이에 99개의 휴게소를 지을 수 있으며 이는 M과 같고, end 값을 mid - 1 = 0으로 다음 단계로 넘어가려니 start 보다 작아지므로 이분 탐색이 종료되게 되므로, 마지막 mid 값인 1이 정상 출력됨을 알 수 있다.

 

• 문제에서 주어진 조건을 보면, '이미 휴게소가 지어진 위치와, 고속도로 양 끝점'은 휴게소를 추가로 지을 수 없다라고 알려주었다. 두 지점이 각각 10과 20이라면 두 지점 사이의 휴게소를 설치할 수 있는 구간은 10~20이 아닌, 11~19로 총 길이는 20 - 10 - 1 = 9 이다. 두 지점의 차에 -1을 추가로 해주어야 한다.

 

---

전체 코드

# 1477

'''
함수 명 : solution
매개변수
    - start : 이분탐색을 위한 구간 중 최소점
    - end : 이분탐색을 위한 구간 중 최대점
역할 : 새로운 휴게소 M개를 지었을 때, 휴게소가 없는 구간의 최댓값으로 올 수 있는 값들 중, 최솟값을 출력해준다. 
'''
def solution(start,end):
    global M
    global locate

    mid = (start + end) // 2 # mid : 새로지을 휴게소 간의 간격
    sum = 0 # sum : 휴게소 간의 간격을 mid로 책정했을 때, 세울 수 있는 총 휴게소의 개수

    # 각 지점 사이 휴게소를 설치할 때, mid 간격으로 휴게소를 설치하면 몇 개 설치할 수 있는지 검사
    for i in range(1,len(locate)): 
        sum += (locate[i] - locate[i-1] - 1) // mid # 이미 휴게소가 있는 지점은 설치할 수 없기에 각 지점 간 거리에서 1을 추가로 빼준다.

   # 합산 값이 M보다 크면 너무 많이 설치할 수 있으므로 mid를 줄여야 함 : end = mid - 1으로 재선언
    if sum > M:
        start = mid + 1
        solution(start, end)

    # 합산 값이 M보다 작으면 더 설치할 수 있으므로 이보다 더 많이 설치하기 위해 mid를 줄여야 함 : end = mid - 1으로 재선언
    # 합산 값이 M과 같으면 간격의 길이를 더 최소화 할 수 있는지 검사하기 위해 mid를 줄여본다 : end = mid - 1
    else:
        end = mid - 1
        if start > end: # end가 start보다 작아지는 시점에 이분 탐색 종료
            print(mid)
            exit()
        solution(start, end)
    

if __name__ == "__main__":
    N,M,L = map(int,input().split())
    
    locate = list(map(int,input().split())) 
    locate.append(0), locate.append(L) # 고속도로의 시작점과 끝점 또한 휴게소를 설치할 수 없기에 휴게소와 같은 '특정 지점'으로 인식
    locate.sort() # 위치 순으로 오름차순 정렬

    # start = 1, end = L 로 초기값 세팅
    # start를  0이 아닌 1로 두는 이유
    # start가 0일 경우, ZeroDivisionError 유발 가능성을 가진 예외가 생김
    solution(1,locate[-1])

 

---

풀이 후기

이분 탐색으로 접근하는 경험이 아직 부족하기에 정말 힘들었던 문제였다. 새로 지을 휴게소 간의 간격의 최솟값을 이분 탐색을 통해 구해야 함을 깨닫는데 까지 시간이 많이 걸렸다. 설상가상으로 초기 start점을 0으로 정했다가, 15%에서 ZeroDivisonError가 날 괴롭히길래 반례를 찾는 데에도 시간이 상당히 많이 걸렸다.