https://st-lab.tistory.com/277
해당 블로그를 참고하여 작성된 포스팅입니다.
이러한 스타일은 정확한 값을 찾는것이 아닌 최대한, 최소한 값을 이진탐색으로 찾는 문제이다.
1. 문제
1-1. 떡볶이 떡 만들기 문제 (이것이 코딩테스트다 책)
오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다.
절단기에 높이 H를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.
예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기를 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm 이다, 손님은 6cm만큼의 길이를 가져간다.
손님이 왔을 때 요청한 총 길이가 M일때, 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.
- 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어진다. (1 <= N <= 1000000, 1 <= M <= 2000000000)
- 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M 이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다. 높이는 10억보다 작거나 같은 양의 정수 또는 0이다.
입/출력 예시
입력
4 6
19 10 17 15출력
151-2. 공유기 설치(백준)
https://www.acmicpc.net/problem/2110
2. 풀이
✨핵심 Point
두 문제의 핵심 포인트는 바로 최소 중의 최대를 뽑아야 한다.
따라서 하한선의 값을 갱신할때마다 answer를 갱신해준다.
2-1. 떡볶이 떡 풀이
- 적어도 M길이만큼. 즉 M보다 같거나 커야한다는 뜻이다.
따라서 start = mid+1에서 answer값을 mid로 갱신해준다.if(length > M) { start = mid + 1; answer = mid; } else { end = mid - 1; }
- start = 0
end = arr[N-1] (가장 긴 길이) 이다
2-2. 공유기 설치 풀이
- 설치가 가능하다면 gap의 크기를 증가시켜 더 큰 값에 대해서도 성공하는지 체크하기위해 다시 탐색을 수행한다.
- C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 만들기 때문에 start = mid+1에서 answer를 갱신해준다.
if(count >= C) { start = mid + 1; answer = mid; } else { end = mid - 1; }
- 초기의 start는 가장 작은 gap인 1이고 end는 가장 큰 갭인 arr[N-1] - arr[0]으로 설정한다.
int start = 1; // min gap.. int end = arr[N - 1] - arr[0]; // max gap
3. 코드
3-1. 떡볶이 떡 코드
import java.util.*;
import java.io.*;
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 arr[] = new int[N];
st = new StringTokenizer(br.readLine(), " ");
for(int n = 0; n < N; n++) {
arr[n] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
//int start = arr[0];
//int end = arr[N - 1];
int start = 0;
int end = arr[N - 1];
int answer = 0;
while(start <= end) {
int mid = (start + end) / 2;
int length = 0;
for(int i = 0; i < N; i++) {
if(arr[i] > mid) {
length += arr[i] - mid;
}
}
/* 없어도 되는 부분.
if(length == M) {
break;
}
*/
if(length > M) {
start = mid + 1;
answer = mid;
} else {
end = mid - 1;
}
}
System.out.println(answer);
}
}
3-2. 공유기 설치 코드
import java.util.*;
import java.io.*;
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 C = Integer.parseInt(st.nextToken());
int arr[] = new int[N];
for(int n = 0; n < N; n++) {
arr[n] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
int start = 1; // min gap..
int end = arr[N - 1] - arr[0]; // max gap
int answer = 0;
while(start <= end) {
int mid = (start + end) / 2;
int value = arr[0];
int count = 1;
for(int i = 0; i < N; i++) {
if(arr[i] >= value + mid) {
value = arr[i];
count++;
}
}
if(count >= C) {
start = mid + 1;
answer = mid;
} else {
end = mid - 1;
}
}
System.out.println(answer);
}
}
3-3. [공유기 설치] 다른 풀이 - UpperBound
import java.util.*;
import java.io.*;
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 C = Integer.parseInt(st.nextToken());
int[] arr = new int[N];
for(int i = 0; i < N; i++){
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
int start = 1;
int end = arr[N-1] - arr[0] + 1;
int answer = 0;
while(start < end){
int mid = (start + end) / 2;
int currentHouse = arr[0];
int count = 1;
for(int i = 0; i < N; i++){
if(arr[i] - currentHouse >= mid){
currentHouse = arr[i];
count += 1;
}
}
if(count < C){
end = mid;
} else{
start = mid + 1;
}
}
System.out.println(end - 1);
}
}
Hi!