[JAVA] 백준 17951번 : 흩날리는 시험지 속에서 내 평점이 느껴진거야

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

---

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[] score = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		int maxScore = 0;
		
		int left = 0, right = Arrays.stream(score).sum();
		while(left <= right) {
			int mid = (left + right) / 2;
			int gCnt = 0, sum = 0;
			for(int s : score) {
				sum += s;
				if(sum >= mid) {
					gCnt++;
					sum = 0;
				}
			}
			if(gCnt >= K) {
				left = mid+1;
				maxScore = mid;
			}
			else
				right = mid-1;
			
		}
		System.out.println(maxScore);
	}

}

💡 이분 탐색

풀이

- 시험지 순서 그대로 K개의 그룹으로 나눈 뒤, 각 그룹의 점수 합을 구하고 -> 그 중 최솟값을 기록

  - 그렇기에 임의의 기준 점수(점수로 처리될 최솟값)을 먼저 결정하고,  반대로 그 기준 점수에 맞춰 그룹을 어떻게 나눌지 결정

• 즉, left( 0 ) ~ right(시험지 점수 총합)으로 진행하며 그룹이 총 몇개 나오는지에 따라 left, right 값을 조정해가며 기준 점수를 조정 해나간다.
  • 기준 점수(mid)가 정해지면, 앞에서부터 점수를 누적합 한 (순서 그대로므로) 뒤 기준을 넘기면 카운팅을 해준다.
  • 카운팅한 그룹 수가 K보다 많으면 기준이 너무 낮다는 것 -> left를 올린다 (같아도 이렇게, 최대 점수 구해야 하므로)
    • 이때 answer도 갱신해준다
  • 카운팅한 그룹 수가 K보다 적으면 기준이 너무 높다는 것 -> right를 내린다