2512번 문제인 예산 문제와 같이 이진 탐색 알고리즘을 사용하였다
while문
제일 긴 랜선 길이(최대값)와 최소값 0을 더한 값에 2를 나누어 중심값을 구하고
K개의 랜선을 해당 중심값으로 나누고 (가진 랜선을 잘라 랜선만들기)
나눈 수를 더하여 만든 랜선의 수를 구한다. (가진 랜선으로 만들어진 랜선 수)
1. 해당 수가 M(만들어야 하는 랜선 수) 보다 작으면
중심값을 줄여 랜선 수를 더 만들어야 하므로 max = mid-1
2. M(만들어야 하는 랜선 수)보다 크면
최적값을 찾기위해 최소값을 올려서 더 길게 랜선을 만들어본다 min = mid
이렇게 탐색 범위를 좁혀나가서 최적의 랜선값을 구한다
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
// 랜선자르기
// https://www.acmicpc.net/problem/1654
public class B1654 {
static int N,M;
static int[] intArr;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine()," ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
intArr = new int[N];
for (int i = 0; i < N; i++) {
intArr[i] = Integer.parseInt(bf.readLine());
}
Arrays.sort(intArr);
binarySearch();
}
private static void binarySearch() {
long max = intArr[N-1];
// 만약 intArr의 최대값이 1이라면
// (min+max)/2가 (0+1)/2 즉 0이 나올 수 있어서
// max의 최소값을 2로 만들어준다
max++;
long min = 0;
while(max > min){
long sum = 0;
long mid = (min+max)/2;
for(int i : intArr){
sum += (i/mid);
}
if(sum < M){
max = mid;
}else{
//upper bound
//sum == M 일때 min을 옮겨준다
min = mid+1;
}
}
System.out.println(min-1);
}
}
'연습문제 > JAVA' 카테고리의 다른 글
[java 백준] 1021 - 회전하는 큐 (0) | 2022.09.03 |
---|---|
[백준 java] 3425 - 고스텍 (0) | 2022.09.02 |
[백준 java] 7662 - 이중 우선순위 큐 (0) | 2022.08.29 |
[백준 java] 1068 - 트리 (0) | 2022.08.27 |
[백준 java] 10845 - 큐 (0) | 2022.08.26 |