👀 문제
https://www.acmicpc.net/problem/1920
👊 도전
1. 설계
- 랜선 길이를 이분 탐색으로 찾는다.
- 구한 mid가 k개의 랜선을 만들 수 있는 경우들 중 최댓값을 리턴한다.
2. 구현 (성공 코드)
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
42
43
44
import java.util.Arrays;
import java.util.Scanner;
/**
* @author HEESOO
*
*/
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
int k=scan.nextInt();
int n=scan.nextInt();
int[] array=new int[k];
for(int i=0;i<k;i++)
array[i]=scan.nextInt();
Arrays.sort(array);
long left=1;
long right=array[k-1];
long mid=0;
long max=0;
while(left<=right) {
mid=(left+right)/2;
long cnt=0;
for(int i=0;i<k;i++)
cnt+=array[i]/mid;
if(cnt>=n) {
left=mid+1;
max=Math.max(max, mid);
}
else {
right=mid-1;
}
}
System.out.println(max);
}
}
3. 결과
🤟 성공 🤟
4. 설명
- 이분탐색 변수들은 long형이어야한다
- 랜선의 길이가 2^31-1이하이므로 랜선 두 개를 더하는 과정에서 int형을 초과한다. 따라서 long형이 필요하다.
- 이분 탐색을 이용한다
- 만들 수 있는 랜선 길이를 이분 탐색으로 구한다.
- 이미 가지고 있는 랜선의 배열 array를 오름차순 정렬한다.
- 구한 mid로 k개의 랜선을 만들 수 있는 지 확인한 후, 맞다면 그 중 최댓값을 max에 저장한다.
- 이분 탐색이 끝나면 max를 리턴한다.