문제풀이/백준
[백준]1477: 휴게소 세우기 - JAVA
빈둥벤둥
2021. 6. 14. 17:29
[백준]1477: 휴게소 세우기

풀이
딱 보자마자 이분탐색을 통해 풀어야 겠다는 생각이 들지 않았어서 풀이하는데 시간이 좀 걸렸다. 이분탐색 유형에 아직 익숙하지 않아서 그런 것 같다.
이 문제는 휴게소의 간격을 기준으로 이분탐색을 진행한 다음 해당 간격이 형성되도록 M개의 휴게소를 생성할 수 있을 때의 최소값을 찾는 문제이다.
예제 입력1을 예시로 살펴보자. 휴게소가 설치될 수 있는구간은 다음과 같다.
1 ~ 81
83 ~ 200
202 ~ 410
412 ~ 554
556 ~ 621
623 ~ 754
756 ~ 799
휴게소의 위치와 0, L을 포함한 값을 배열에 담아 정렬시켜준다. (범위 값 계산을 하기 위해)
이때, 휴게소 간격의 최소값은 0, 최대값은 L이 된다.
이제 이분 탐색을 시작한다. 탐색하며 찾는 값은 휴게소 간격이 되며 mid값으로 설정한다.
can_make 함수에서 휴게소 간격을 mid로 설정했을때, 몇 개의 휴게소를 설치할 수 있는지 count하고 설치해야 하는 휴게소 개수인 M개보다 크다면 큰 범위를, 작다면 작은 범위를 이분 탐색한다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
import java.util.*;
public class Main {
static int n, m, l;
static ArrayList<Integer> list;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
l = scan.nextInt();
list = new ArrayList<>();
list.add(0); //제일 작은 값
list.add(l); //제일 큰 값
for(int i = 0; i < n; i++) {
list.add(scan.nextInt());
}
Collections.sort(list);
int left = 0;
int right = l;
while(left <= right) {
int mid = (left + right) / 2; //휴게소의 간격
if(can_make(mid)) left = mid + 1;
else right = mid - 1;
}
System.out.println(left);
}
public static boolean can_make(int mid) {
int count = 0;
for(int i = 1; i < list.size(); i++) {
count += (list.get(i) - list.get(i - 1) - 1) / mid;
}
if(count > m) return true;
return false;
}
}
|
cs |