문제
넓은 시험 범위와 어려운 과제로 유명한 '운영체제로 보는 데이터베이스시스템 알고리즘' 수업은 시험지가 너무 많아 실내에서는 시험을 치를 수 없어서 야외에서 시험을 진행한다. 해당 수업의 수강생인 현수는 오랜 시간에 걸쳐 풀 수 있는 모든 문제를 풀었고 제출만을 남겨두고 있었다. 그러나 갑자기 불어오는 강풍에 현수의 시험지가 모두 날아가 버렸고, 날아간 시험지를 줍는 동안 남은 시간을 다 써버리고 말았다.
시험지에 명시된 규칙 중에는 채점하는 조교의 편의를 위해 시험지를 반드시 순서대로 제출하라는 규칙이 있는데, 이 규칙 때문에 현수는 힘들게 치른 시험이 0점 처리될 위기에 빠지게 되었다!
그러나, 마음씨 좋은 조교인 주찬이는 평소 수업에 열심히 참여한 현수에게 한 번의 기회를 주기로 했다. 규칙은 규칙이므로 많은 점수를 줄 수는 없고, 시험지를 현재 순서 그대로 K개의 그룹으로 나눈 뒤 각각의 그룹에서 맞은 문제 개수의 합을 구하여 그 중 최솟값을 시험 점수로 하기로 하였다. 현수가 이번 시험에서 받을 수 있는 최대 점수를 계산하는 프로그램을 작성하자.
현수는 모르는 문제를 아예 풀지 않기 때문에 현수가 푼 문제는 모두 맞았다고 생각할 수 있으며, 조교는 마음씨가 좋아서 자신이 줄 수 있는 최대한의 점수를 준다.
입력
첫 번째 줄에 시험지의 개수 N과 시험지를 나눌 그룹의 수 K가 정수로 주어진다. (1 <= K <= N <= 10^5)
두 번째 줄에 각 시험지마다 맞은 문제의 개수 x가 정수로 주어진다 (0 <= x <= 20)
출력
현수가 받을 수 있는 최대 점수를 출력한다.
풀이
N과 K가 충분히 크기 때문에 가능한 모든 기준 점수를 직접 시도해 보거나, 그룹을 나누는 모든 경우를 탐색하는 방식은 어렵다. 그래서 이 문제는 "최소 그룹 점수를 얼마까지 보장할 수 있는가"를 기준으로 이분 탐색하는 것이 핵심이다.
어떤 값 mid를 후보 점수라고 하자. 그러면 문제는 "모든 그룹의 점수가 적어도 mid가 되도록 시험지를 나눌 수 있는가?"라는 판정 문제로 바뀐다. 이 판정은 앞에서부터 점수를 누적하다가 합이 mid 이상이 되는 순간 하나의 그룹을 끊는 그리디 방식으로 확인할 수 있다.
이렇게 했을 때 만들 수 있는 그룹 수가 K개 이상이면 mid는 충분히 가능한 값이다. 그룹을 더 많이 만들 수 있다는 것은 몇몇 그룹을 합쳐서 정확히 K개로도 만들 수 있다는 뜻이므로, 더 큰 점수도 가능한지 오른쪽 구간을 탐색하면 된다. 반대로 K개를 만들 수 없다면 mid가 너무 큰 것이므로 왼쪽으로 줄여야 한다.
즉 답이 될 수 있는 점수 범위에서 이분 탐색을 돌리고, 각 mid마다 선형으로 그룹 수를 세면 된다. 주신 말처럼 입력 크기 때문에 결국 이분 탐색이 필요한 문제였고, 판정 함수만 깔끔하게 만들면 구현은 단순한 편이다.
코드
import java.io.*;
import java.util.*;
public class Main {
private static int N, K, total;
private static int[] test;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
test = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
test[i] = Integer.parseInt(st.nextToken());
total += test[i];
}
System.out.println(solve());
}
private static int solve() {
int left = 0;
int right = total;
int ans = 0;
while (right >= left) {
int mid = (left + right) / 2;
int sum = 0;
int cnt = 0;
for (int num : test) {
sum += num;
if (sum >= mid) {
cnt++;
sum = 0;
}
}
if (cnt >= K) {
left = mid + 1;
ans = mid;
}
else right = mid - 1;
}
return ans;
}
}복잡도
- 시간 복잡도:
S는 전체 점수 합
- 공간 복잡도:
마무리
그룹을 어떻게 자를지 직접 고민하기 시작하면 복잡해지지만, "최소 점수를 정해 두고 가능한지만 보자"로 바꾸면 전형적인 매개 변수 탐색 문제가 된다. 답 자체를 이분 탐색한다는 관점을 떠올리는지가 핵심이다.
