안녕하세요. 오늘은 백준의 1477. 휴게소 세우기문제를 풀어보겠습니다.
1. 문제 링크
https://www.acmicpc.net/problem/1477
2. 문제 풀이
✔ 이진탐색 전 휴게소 위치 정렬
휴게소 사이의 거리이기 때문에, 휴게소 위치에 처음 0, 마지막 L을 추가로 넣어줍니다. 또한 이진탐색을 진행하기 위해 휴게소 위치를 sort해줍니다.
✔ 휴게소 binarySearch(이진탐색) 이용
휴게소가 없는 구간의 최댓값을 이진탐색으로 찾아주면 됩니다. 이진탐색을 수행하는 값은 "휴게소 사이의 거리" 이며, 휴게소 사이의 거리가 mid라고 할 때, 현재 세워진 휴게소 사이에 새로 끼워넣을 수 있는 휴게소 수를 체크합니다.
끼워넣을 수 있는 휴게소의 갯수가 M보다 크면, 조건을 충족하기 때문에 더 넓은 범위에서 탐색합니다.(left = mid + 1)
끼워넣을 수 있는 휴게소의 갯수가 M보다 작으면, 조건을 충족하지 못하기 때문에 더 좁은 범위에서 탐색합니다.(right = mid - 1)
3. 입출력 예시 설명
문제에서 주어진 입출력 에시 중 하나를 가지고 설명해보겠습니다.
입력
6 7 800
622 411 201 555 755 82
출력
70
✔ 휴게소 간 거리
- L : 800
- M : 7
- N : 6
- 휴게소 오름차순 sort: 0 82 201 411 555 622 755 800
- 휴게소 간 거리: 82 119 210 144 67 133 45
✔ mid: 400 left: 1 right: 800
mid = (left + right) / 2 이므로, mid = 400입니다.
휴게소 간 거리가 400이 넘는 경우는 없으므로, sum은 0입니다.
sum <= M이므로, right = mid - 1로 위쪽 범위를 줄여줍니다.
✔ mid: 199 sum: 1, left: 1 right: 399
mid = (left + right) / 2 이므로, mid = 199입니다.
휴게소 간 거리가 199이 넘는 경우는 1이므로, sum은 1입니다.
sum <= M이므로, right = mid - 1로 위쪽 범위를 줄여줍니다.
✔ mid: 99 sum: 5, left: 1 right: 198
mid = (left + right) / 2 이므로, mid = 99입니다.
휴게소 간 거리가 99이 넘는 경우는 4개이며, 그 중 210은 휴게소 간 거리가 99가 되기 위해선 하나를 더 세워야 하기 때문에 sum은 5입니다.
sum <= M이므로, right = mid - 1로 위쪽 범위를 줄여줍니다.
✔ mid: 49 sum: 12, left: 1 right: 98
mid = (left + right) / 2 이므로, mid = 49입니다.
휴게소 간 거리가 49이 넘는 경우는 6개이며, 그 중 휴게소 간 거리가 49가 되기 위해 2개 이상의 휴게소를 세워야 하는 것도 있기 때문에 sum은 12입니다.
sum > M이므로, left = mid + 1로 아래쪽 범위를 줄여줍니다.
✔ mid: 74 sum: 6, left: 50 right: 98
mid = (left + right) / 2 이므로, mid = 74입니다.
휴게소 간 거리가 74이 넘는 경우는 5이며, 그 중 210은 휴게소 간 거리가 74보다 작기 위해 2개의 휴게소를 세워야 합니다. 따라서 sum은 6입니다.
sum <= M이므로, right = mid - 1로 위쪽 범위를 줄여줍니다.
✔ mid: 61 sum: 10, left: 50 right: 73
mid = (left + right) / 2 이므로, mid = 61입니다.
휴게소 간 거리가 61이 넘는 경우는 6이며, 그 중 휴게소 간 거리가 61가 되기 위해 2개 이상의 휴게소를 세워야 하는 것도 있기 때문에 sum은 10입니다.
sum > M이므로, left = mid + 1로 아래쪽 범위를 줄여줍니다.
✔ mid: 67 sum: 8, left: 62 right: 73
mid = (left + right) / 2 이므로, mid = 67입니다.
휴게소 간 거리가 67이 넘는 경우는 6이며, 그 중 휴게소 간 거리가 67가 되기 위해 2개 이상의 휴게소를 세워야 하는 것도 있기 때문에 sum은 8입니다.
sum > M이므로, left = mid + 1로 아래쪽 범위를 줄여줍니다.
✔ mid: 70 sum: 7, left: 68 right: 73
mid = (left + right) / 2 이므로, mid = 70입니다.
휴게소 간 거리가 70이 넘는 경우는 5이며, 그 중 휴게소 간 거리가 70가 되기 위해 2개 이상의 휴게소를 세워야 하는 것도 있기 때문에 sum은 7입니다.
sum <= M이므로, right = mid - 1로 위쪽 범위를 줄여줍니다.
✔ mid: 68 sum: 8, left: 68 right: 69
mid = (left + right) / 2 이므로, mid = 68입니다.
휴게소 간 거리가 68이 넘는 경우는 5이며, 그 중 휴게소 간 거리가 68가 되기 위해 2개 이상의 휴게소를 세워야 하는 것도 있기 때문에 sum은 8입니다.
sum > M이므로, left = mid + 1로 아래쪽 범위를 줄여줍니다.
✔ mid: 69 sum: 8, left: 69 right: 69
mid = (left + right) / 2 이므로, mid = 69입니다.
휴게소 간 거리가 69이 넘는 경우는 5이며, 그 중 휴게소 간 거리가 69가 되기 위해 2개 이상의 휴게소를 세워야 하는 것도 있기 때문에 sum은 8입니다.
sum > M이므로, left = mid + 1로 아래쪽 범위를 줄여줍니다.
✔ 정답 70 출력
위의 로직까지 수행하고 나서, left: 70, right: 69로, left > right가 되어 while문을 빠져나옵니다. left값인 70을 return하며, 70이 출력됩니다.
4. 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int L = Integer.parseInt(st.nextToken());
int[] rest = new int[N + 2];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 1; i <= N; i++) {
rest[i] = Integer.parseInt(st.nextToken());
}
// 도로의 시작 , 끝도 휴게소로 넣어줘야 함
rest[0] = 0;
rest[N + 1] = L;
Arrays.sort(rest);
System.out.println(binarySearch(rest, N, M, L));
}
// 0 82 201 411 555 622 755 800
// 휴게소 m개를 추가로 지었을 때, 각 휴게소 사이의 거리의 최대값이 d 이하가 되게 만들 수 있는가? => T / F
// M개를 설치했을 때 각 휴게소끼리의 거리의 최대값을 mid라고 하자. 조건을 충족하는 최적의 mid를 찾아가는 방식이다.
// 만약 400일때 조건을 충족한다면 0~399는 볼필요도 없다. 401부터 최대값을 찾아나간다.
private static int binarySearch(int[] rest, int N, int M, int L) {
int left = 1;
int right = L;
while (left <= right) {
int mid = (left + right) / 2;
int sum = 0;
// sum : 휴게소 사이 거리가 mid라고 했을때, 현재 세워진 휴게소 사이에 새로 끼워 넣을 수 있는 휴게소 수.
for (int i = 1; i < N + 2; i++) {
sum += (rest[i] - rest[i - 1] - 1) / mid;
}
// System.out.println("mid: "+mid+" sum: "+sum+", L: "+left+" right: "+right);
if (sum > M) { // 현재 mid의 거리 차이가 가능하다면 => 더 최대값을 찾기 위해 더 넓은 범위 탐색
left = mid + 1;
} else { // 더 적게 세워야 하면 간격을 줄임
right = mid - 1;
}
}
return left;
}
}5. 느낀점
이진탐색으로 분류되어 있는 문제인데, 어느 걸 pivot으로 설정해서 이진탐색할지 감이 잡히지 않았습니다. 또한, 이진탐색 로직에서 어떨 때 왼쪽 부분을 탐색하고 어떨 때 오른쪽 부분을 탐색해야할지 판단하는 로직도 생각하지 못했습니다.
다음부터는 이진탐색 문제를 풀 때 어느 걸 pivot으로 설정할지부터 정해야겠다는 생각이 들었습니다. 그리고 상대적으로 이진탐색 문제를 많이 풀어보지 않아서, 문제를 좀 더 풀어보면서 감을 익혀야겠다는 생각이 들었습니다.
[참고한 곳]
https://namhandong.tistory.com/m/199
https://github.com/tony9402/baekjoon
