✨ 언어: Java, 수행시간: 160ms, 메모리: 14432KB, 소요 시간: 60분
🗝️ 키워드: 이분 탐색, 매개 변수 탐색
➊ 문제 정의
길이가 L인 롤케이크가 있다.
이 롤케이크에는 자를 수 있는 지점이 M개 있으며 이 중 Q개를 선택해서 잘라야 한다.
만약 70cm 길이의 롤케이크에 자를 수 있는 지점이 5군데(10cm, 20cm, 35cm, 55cm, 60cm)가 있다고 하자.
위 그림과 같이 5군데의 지점 중 3군데를 선택해서 잘라야 한다고 가정해보자!
이 문제에서 구하고자 하는 답은
가장 작은 조각의 길이는 최대가 되도록 자르는 것이다.
따라서 아래와 같이 20cm, 35cm, 55cm 지점을 자르면
작은 조각의 길이는 15cm로 최대가 된다.
이처럼 가장 작은 조각이 최대가 될 수 있도록 Q개를 선택해서 잘라보자!
➋ 문제 아이디어
① 완전 탐색이 가능할까?
가장 쉽게 풀 수 있는 방법으로는 완전 탐색을 생각해볼 수 있다.
자를 수 있는 지점 M개 중에서 Q개를 선택하는 모든 조합(mCq)을 구하고
각 조합마다 작은 조각의 길이를 구한다.
재귀를 통하여 mCq의 조합을 구할 때 시간복잡도 O(2^m)가 된다.
문제에서 주어진 범위는 다음과 같다.
(1 ≤ N ≤ M ≤ 1,000, 1 < L ≤ 4,000,000)
만일 M=1000일 경우 시간복잡도는 O(2^1000)이 되며 이는 매우 큰 연산이다.
따라서 위의 방법으로는 제한 시간 내에 문제를 해결할 수 없다.
또 아래와 같은 방법으로도 완전 탐색을 할 수 있다. 💭
롤 케이크가 L의 길이를 가지므로,
ⓐ 조각의 길이가 1, 2, 3, ..., L인 경우를 모두 생각해본다.
ⓑ 각 경우에 대하여, 자를 수 있는 지점 M개 중에서 Q개를 선택하는 게 가능한지 따진다.
ⓒ 위 연산을 N번 수행한다. (자르는 횟수인 Q가 N번 주어지기 때문!)
따라서 L × M × N 번의 연산을 수행하게 되고
L × M × N번 = 4,000,000 × 1,000 × 1,000 = 4조의 연산이 필요하다.
자바에서는 1초에 약 10억 번의 연산이 가능하므로
위의 완전 탐색 방식도 불가능하다.
② 이분 탐색 💡
그렇다면 어떻게 하면 연산을 줄일 수 있을까?
문제 해결 아이디어는 다음과 같다.
ⓐ 조각의 길이가 1, 2, 3, ..., L인 경우를 모두 생각해보는 대신에,
탐색 범위를 절반씩 좁혀가며 이분 탐색을 하는 것이다!
위와 같이 이분 탐색을 진행하면,
1,000 × 1,000 × log 4,000,000 = 약 21,940,000번의 연산을 수행하게 되며
제한 시간 내에 문제 해결이 가능하다!
➌ 문제 해결
그렇다면 문제를 푸는 알고리즘은 다음과 같다.
ⓐ 1 ~ L 범위 내에서 이분 탐색을 하며 조각의 길이를 정한다.
ⓑ 각 경우에 대하여, 자를 수 있는 지점 M개 중에서 Q개를 선택하는 게 가능한지 따진다.
ⓒ 위 연산을 N번 수행한다. (자르는 횟수인 Q가 N번 주어지기 때문!)
아래는 ⓐ에 대한 코드이다.
left = 1, right = L 로 초기화한다.
이때 left에서 right 사이가 탐색 범위이다.
탐색 범위의 중간값(mid)에 대하여 🚩 조건 을 만족하는지 따진다.
위 조건이란 롤케이크의 모든 조각이 mid 길이 이상이 되도록 Q번 자를 수 있는지를 확인하는 것이다.
만약 Q = 3, mid = 20 라면
조각들이 20cm 이상이 되도록 3번을 자르는 것이다.
그렇다면 조건 만족 여부를 어떻게 확인할 수 있을까?
다음과 같이 롤케이크의 자를 수 있는 지점을 for문으로 탐색한다.
10, 20, 35, 55, 60 지점에서 자를지 말지를 결정한다.
이때 이전에 잘랐던 지점과 비교하여 20cm 이상 차이가 나면 자른다.
Q = 3, mid = 20 라는 위 예시에서는
롤케이크를 3번 자를 수 없으므로 조건을 만족하지 않는다.
조각의 길이를 줄일 필요가 있으므로 mid 이하의 범위를 재탐색한다.
이처럼 🚩 조건을 만족하면 중간값 이상의 범위를 탐색하고,
그렇지 않다면 중간값 이하의 범위를 탐색한다.
left > right 가 되면 이진 탐색을 종료한다.
➍ 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class 케이크자르기 {
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static StringTokenizer tokens;
private static StringBuilder sb = new StringBuilder();
private static int N; // 자르는 횟수의 목록 길이
private static int M; // 자를 수 있는 지점의 개수
private static int L; // 롤케이크의 길이
private static int[] S; // 자를 수 있는 지점
private static int[] Q; // 자르는 횟수
// cutCount 만큼 잘라서 모든 조각이 len 이상이 될 수 있는지 여부 반환
private static boolean check(int len, int cutCount) {
int count = 0; // 현재 자른 횟수
int prevCutPoint = 0; // 마지막으로 자른 지점
int differ = 0;
for (int i = 0; i < M; i++) {
differ = S[i] - prevCutPoint;
if (differ >= len) {
count++;
prevCutPoint = S[i];
}
}
// 마지막 조각 len 이상인지 확인
differ = L - prevCutPoint;
if (!(differ >= len)) {
count--;
}
return count >= cutCount;
}
// cutCount 만큼 잘랐을 때 가장 작은 조각의 길이의 최댓값 반환
// 가장 작은 조각의 길이의 최댓값을 이진 탐색으로 찾기
private static int binarySearch(int cutCount) {
int answer = 0;
int left = 1;
int right = L;
while (left <= right) {
int mid = (left + right) / 2;
if (check(mid, cutCount)) {
answer = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return answer;
}
private static void solution() {
for (int i = 0; i < N; i++) {
int answer = binarySearch(Q[i]);
sb.append(answer).append("\n");
}
}
private static void init() throws IOException {
tokens = new StringTokenizer(br.readLine());
N = Integer.parseInt(tokens.nextToken());
M = Integer.parseInt(tokens.nextToken());
L = Integer.parseInt(tokens.nextToken());
S = new int[M];
Q = new int[N];
for (int i = 0; i < M; i++) {
S[i] = Integer.parseInt(br.readLine());
}
for (int i = 0; i < N; i++) {
Q[i] = Integer.parseInt(br.readLine());
}
}
public static void main(String[] args) throws IOException {
init();
solution();
System.out.println(sb);
}
}