이분탐색 메커니즘
이분 탐색 문제를 접근할 때, 백준 블로그를 참고하면 정말 도움이 된다.
블로그 내용을 요약하면,
"결정 문제"를 풀어낼 때 이분적으로 답이 두 구간으로 나뉠 때 이분 탐색 알고리즘을 이용할 수 있다는 것이다. 또한, 많은 최적화 문제를 풀어낼 수 있음.
최적화 문제란?
어떤 조건 Check(x)를 만족하는 x의 최댓값 또는 최솟값을 찾는 문제를 말함. 이 경우, Check(x)가 x에 대해 이분적이면 이분 탐색을 사용할 수 있다는 것이다.
내용 핵심 정리
- [lo, hi]가 Check(lo) ≠ Check(hi)가 되도록 구간을 설정
- while(lo + 1 < hi) 동안 mid = (lo + hi) / 2에서 Check(mid) = Check(lo)라면 lo = mid, 아니라면 hi = mid
- 구한 경계에서 답이 lo인지 hi인지 생각해보고 출력하기
문제
https://www.acmicpc.net/problem/17951
내용을 요약하자면 시험지의 개수 N과 나눌 그룹의 수 K가 정수로 주어졌을 때, K개의 그룹으로 나눈 뒤 각각의 그룹에서 맞은 문제의 개수의 합을 구하여 그중 최솟값을 시험 점수로 하기로 하였다.
따라서 우리가 구해야 할 핵심은 K개의 그룹으로 나눌 수 있을 때, 최솟값들 중 최댓값을 구해야 한다는 것이다.
주의사항: 시험지를 현재 순서 그대로 K개의 그룹으로 나눈다는 것이다.
정렬되어 있지 않는 시험지 점수들 때문에 어떻게 이분 탐색으로 최적화할 수 있을까?를 고민할 수 있지만 이 문제의 접근 핵심은 최소 점수와 최대 점수의 합을 이용하여 각 그룹이 가질 수 있는 임계값, 즉 최댓값을 지정해주면 된다
- 내용 핵심 정리에서 설명한대로, 경계를 설정해야 한다.
왼쪽 경계, 즉 lo에 대해 0으로 설정하자. 그러면 각 그룹이 가질 수 있는 최댓값이 0으로 지정된다. 이 말은 시험 점수 각각 하나씩이 그룹이 되어버린다. - hi에 대해 점수의 총합 + 1 로 설정하자. 그러면 각 그룹이 가질 수 있는 최댓값이 전체 총합 + 1로 지정된다. 이 말은 모든 시험 점수를 더해도 최댓값을 넘지 못하기 때문에 하나의 그룹만 생성된다.
그 결과, 왼쪽 경계는 K개보다 그룹이 많거나 같다를 항상 만족하고, 오른쪽 경계는 K개보다 작다. 이에 대한 check 함수를 작성하자면
public static boolean check(int K, int mid, int[] scores) {
int sum = 0, cnt = 0;
for (int score : scores) {
sum += score;
if (sum >= mid) {
cnt++;
sum = 0;
}
}
return cnt >= K;
}이를 말로 설명하자면, cnt >= K 를 만족한다는 것은 그룹의 최댓값으로 설정된 mid로는 K개 이상의 그룹을 만들 수 있다는 것이기 때문에 lo = mid로 만들어서 더 큰 왼쪽 경계를 만들어주면 된다. 그 결과, cnt == K가 될 때 까지 왼쪽 경계를 TTTTTTTT.. FFF 로 만들어간다는 것이다.
반대로 cnt < K보다 작다면 반대로 hi = mid가 되어 경계를 조절한다.
lo + 1 == hi 가 되었을 떄, 경계에서 어느쪽이 정답일까?를 생각하고 정답을 구하면 된다.
해당 문제에서는 왼쪽 경계가 조건을 만족할 때까지 최대로 조절하기 때문에 lo가 정답이 된다.
전체 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[] scores = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int min = 0, max = 1;
for (int score : scores) {
max += score;
}
while (min + 1 < max) {
int mid = (min + max) / 2;
if (check(K, mid, scores)) {
min = mid;
} else {
max = mid;
}
}
System.out.println(min);
}
public static boolean check(int K, int mid, int[] scores) {
int sum = 0, cnt = 0;
for (int score : scores) {
sum += score;
if (sum >= mid) {
cnt++;
sum = 0;
}
}
return cnt >= K;
}
}