[BOJ] 백준 17961 흩날리는 시험지 속에서 내 평점이 느껴진거야 (Java)

 

https://www.acmicpc.net/problem/17951

 

문제 설명

Parametric Search (매개변수 탐색) 문제이다.

주어진 시험지 점수를 나누어 여러 부분합을 만들 때, 최소 부분합이 최대가 되도록 나누는 문제이다.

 

누적합을 이용해 각 구간의 합을 계산하고, 구간의 합이 현재 mid 값보다 크거나 같으면 해당 구간을 하나로 묶고 구간의 개수를 증가시킨다.

그 후, mid 값을 변경하며 원하는 개수의 구간이 나오도록 하고, 이때 최소 부분합이 최대가 되는 mid 값을 찾아내면 된다.

 

문제 풀이

8 3
12 7 19 20 17 14 9 10

 

k값이 3인경우를 생각해보자

 

첫 번째 이진 탐색:

• start = 0, end = 108, mid = (0 + 108) / 2 = 54

부분합 계산:

• 첫 번째 구간: 12 + 7 + 19 + 20 = 58 (54 이상)
• 세 번째 구간: 17 + 14 + 9 + 10 = 50 (54 미만)

 

구간을 3개 이상의 구간을 만들 수 없으므로, mid = 54는 적합하지 않다.

mid 값을 줄여야 한다.

 

두 번째 이진 탐색:

• start = 0, end = 53, mid = (0 + 53) / 2 = 26

부분합 계산:

• 첫 번째 구간: 12 + 7 + 19 = 38 (26 이상)
• 두 번째 구간: 20 + 17 = 37 (26 이상)
• 세 번째 구간: 14 + 9 + 10 = 33 (26 이상)

 

이때는 3개의 구간을 만들 수 있다. mid = 26은 유효하다. 최소 부분합은 33이다.

mid 값을 더 크게 설정하여 최소 부분합을 키워보자.

 

세 번째 이진 탐색:

• start = 27, end = 53, mid = (27 + 53) / 2 = 40

부분합 계산:

• 첫 번째 구간: 12 + 7 + 19 + 20 = 58 (40 이상)
• 두 번째 구간: 17 + 14 + 9 = 40 (40 이상)
• 세 번째 구간: 10  (40 미만)

 

구간을 3개 이상의 구간을 만들 수 없으므로, mid = 40은 적합하지 않다.

mid 값을 줄여야 한다.

 

네 번째 이진 탐색:

• start = 27, end = 39, mid = (27 + 39) / 2 = 33

부분합 계산:

• 첫 번째 구간: 12 + 7 + 19 = 38 (33 이상)
• 두 번째 구간: 20 + 17 = 37 (33 이상)
• 세 번째 구간: 14 + 9 + 10 = 33 (33 이상)

 

이때도 3개의 구간을 만들 수 있다. mid = 33은 유효하다. 최소 부분합은 33이다.

mid 값을 더 크게 설정하여 최소 부분합을 키워보자.

 

다섯 번째 이진 탐색:

• start = 34, end = 39, mid = (34 + 39) / 2 = 36

부분합 계산:

• 첫 번째 구간: 12 + 7 + 19 = 38 (36 이상)
• 두 번째 구간: 20 + 17 = 37 (36 이상)
• 세 번째 구간: 14 + 9 + 10 = 33 (36 미만)

 

구간을 3개 이상의 구간을 만들 수 없으므로, mid = 36은 적합하지 않다.

mid 값을 줄여야 한다.

 

여섯 번째 이진 탐색:

• start = 34, end = 35, mid = (34 + 35) / 2 = 34

부분합 계산:

• 첫 번째 구간: 12 + 7 + 19 = 38 (34 이상)
• 두 번째 구간: 20 + 17 = 37 (34 이상)
• 세 번째 구간: 14 + 9 + 10 = 33 (34 미만)

 

구간을 3개 이상의 구간을 만들 수 없으므로, mid = 34은 적합하지 않다.

mid 값을 줄여야 한다.

 

일곱 번째 이진 탐색:

• start = 34, end = 33
• start <= end 가 성립하지 않아서 탐색이 종료된다.

 

☆ 이진탐색 수행시 등호가 어디에 들어가야 하는지 ☆

이진 탐색을 수행할 때 등호가 어디에 들어가야하는지 헷갈렸다.

if (cnt >= k) {
    start = mid + 1;
} else {
    end = mid - 1;
}

 

• cnt >= k 조건은 cnt가 k와 같거나 클 때를 포함한다.
• cnt == k일 때도 start를 증가시켜 탐색 범위를 오른쪽으로 좁힌다.
• 따라서, cnt == k일 때도 mid를 무시하고 오른쪽 영역을 계속 탐색한다.
• 즉, 최대값을 구하거나 특정 조건을 만족하는 값의 상한(upper bound)을 찾는 경우 사용한다.

 

if (cnt > k) {
    start = mid + 1;
} else {
    end = mid - 1;
}

 

• cnt > k 조건은 cnt == k일 때 end를 감소시켜 탐색 범위를 왼쪽으로 좁힌다.
• 이 방식은 최소값을 구하거나 특정 조건을 만족하는 값의 하한(lower bound)을 찾는 경우 적합하다.

 

 

전체 코드

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer token;

	static int n, k;
	static int[] scores;
	static int sum;
	static int start, end, mid;
	static long ans, tempAns;

	public static void sol() {
		start = 0;
		end = sum;
		while (start <= end) {
			mid = (start + end) / 2;
			int cnt = 0, temp = 0;
			tempAns = Integer.MAX_VALUE;
			for (int i = 0; i < n; i++) {
				temp += scores[i];
				if (temp >= mid) {
					cnt++;
					tempAns = Math.min(tempAns, temp);
					temp = 0;
				}
			}

			// 등호는 어디에 들어가야 하는지
			if (cnt >= k) { // 점수의 최대값 -> mid 의 상한
				start = mid + 1;
				ans = Math.max(ans, tempAns);
			} else {
				end = mid - 1;
			}
		}
		output.append(ans);
	}

	public static void init() throws Exception {
		sum = 0;
		ans = 0;
		token = new StringTokenizer(input.readLine());
		n = Integer.parseInt(token.nextToken());
		k = Integer.parseInt(token.nextToken());
		token = new StringTokenizer(input.readLine());
		scores = new int[n];
		for (int i = 0; i < n; i++) {
			scores[i] = Integer.parseInt(token.nextToken());
			sum += scores[i];
		}
	}

	public static void main(String[] args) throws Exception {
		init();
		sol();
		System.out.println(output);
	}

}