[알고리즘 일기 - 파이썬] 187. 휴게소 세우기
1477번: 휴게소 세우기
첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다.
www.acmicpc.net
Baekjoon 1477. 휴게소 세우기
[파이썬(python) - 이분탐색]
다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다.
다솜이는 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 휴게소는 정수 위치에만 세울 수 있다.
다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한다. 다솜이는 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. (반드시 M개를 모두 지어야 한다.)
예를 들어, 고속도로의 길이가 1000이고, 현재 휴게소가 {200, 701, 800}에 있고, 휴게소를 1개 더 세우려고 한다고 해보자.
일단, 지금 이 고속도로를 타고 달릴 때, 휴게소가 없는 구간의 최댓값은 200~701구간인 501이다. 하지만, 새로운 휴게소를 451구간에 짓게 되면, 최대가 251이 되어서 최소가 된다.
입력
첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다.
출력
첫째 줄에 M개의 휴게소를 짓고 난 후에 휴게소가 없는 구간의 최댓값의 최솟값을 출력한다.
입력 예시
6 7 800
622 411 201 555 755 82
출력 예시
70
❧ 정답
🔎IDEA) 이분탐색 - 한번에 m개의 휴게소를 세운다.
[Line 5 - 7]
👉 휴게소를 세울 수 있는 구간이 0과 l사이(정수)이므로 현재 휴게소의 위치말고도 0과 l 또한 휴게소 위치로 포함시켜준다.
(문제에 보면 고속도로의 끝에는 휴게소를 세울 수 없다고 나와있으므로 0과 l에도 휴게소가 있다고 가정한다.)
👉 현재 휴게소의 위치가 무작위로 입력되었으므로 위치순으로 정렬을 수행한다.
[Line 9]
👉 시작지점 1을 start로 지정하고 l을 end로 지정한 뒤 이분 탐색을 시작한다.
[Line 13 - 15]
👉 최대 mid간격만큼 휴게소를 설치했을 때의 개수를 변수 cnt에 저장한다.
👉 이때 원래 휴게소가 설치된 위치에는 또 휴게소를 설치할 수 없으므로 두 휴게소간 간격에서 1을 빼준다.
Ex. 2와 5에 휴게소가 설치 되어있다고 했을 때 두 휴게소 사이에 휴게소를 설치할 수 있는 위치는 3과 4 두 곳이다.
∴ 5(arr[i]) - 2(arr[i - 1]) -1
[Line 16 - 19]
👉 설치된 휴게소의 개수가 m보다 크면 휴게소 설치 간격을 늘리고(start = mid + 1) 설치된 휴게소의 개수가 m보다 작으면 휴게소 설치 간격을 줄인다.(end = mid - 1)
👉 설치된 휴게소 개수가 m일때의 간격 값을 저장하기 위해 rst에 mid값을 갱신해준다.
[Line 22]
👉 start지점과 end지점이 교차될 때가 가장 최대값이므로 이때의 mid값을 출력한다.
TRY 1
🔎 모두 같은 간격으로 설치한다는 풀이를 생각하지 못하고 원래 간격에서 반드시 n//k만큼 설치할 걸로 문제를 접근했다.
🔎 이분탐색 문제에서는 mid값을 뭘로 설정할 지 정하는 게 가장 중요하다.