흩날리는 시험지 속에서 내 평점이 느껴진거야 17951

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

이 문제는 이해하는데 어려움을 많이 겪었다
문제가 요구하는것은
시험지의 순서를 변경할 수 없다
시험지를 그룹으로 묶는다 그룹의 합계를 구한다. 합계중 가장 작은 값이 현수의 점수가 된다.
그러므로 이 점수를 최대로 높이기 위한 노력이 필요하다.

어떻게 합계중에 최소값이 최대가 되도록 할 수 있을까?
그룹의 합계점수간에 편차가 작을 수록 현수가 얻을 수 있는 점수가 커지게 된다.

예제입력에서
8 2
12 7 19 20 17 14 9 10

시험지의 순서를 바꾸지 못한다면 만들 수 있는 그룹의 경우는

    그룹 1: 12, 그룹 2: 7, 19, 20, 17, 14, 9, 10
    그룹 1: 12, 7, 그룹 2: 19, 20, 17, 14, 9, 10
    그룹 1: 12, 7, 19, 그룹 2: 20, 17, 14, 9, 10
    그룹 1: 12, 7, 19, 20, 그룹 2: 17, 14, 9, 10
    그룹 1: 12, 7, 19, 20, 17, 그룹 2: 14, 9, 10
    그룹 1: 12, 7, 19, 20, 17, 14, 그룹 2: 9, 10
    그룹 1: 12, 7, 19, 20, 17, 14, 9, 그룹 2: 10

위의 그룹중에서 그룹 점수의 최소값이 최대가 되도록 하면된다

mid 라는 점수를 임으로 세팅하자
sum이라는 변수선언
for문으로 돌면서 시험지의 점수를 sum에 더한다
sum >= mid 되면 gcount를 ++ 해준다 그룹개수를 1+ 해주는것이다

이렇게해서 gcount 가 K 보다 크다면 mid 의 값을 높이고
gcount 가 K 보다 작다면 mid 의 값을 낮추면서 mid 값을 찾는다

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

public class Main {

    public static void main(String[] args) throws IOException{

        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 sum = 0;//모든 시험지 총합
        int[] arr = new int[n];

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            sum += arr[i];
        }

        int left = 0;
        int right = sum;
        int mid = 0;

        while(left <= right){

            int gcount = 0;//그룹 개수
            int gsum = 0;//그룹별 총합
            mid = (left+right)/2;
            for (int i = 0; i < n; i++) {

                gsum += arr[i];
                if(gsum >= mid){
                    gcount++;
                    gsum = 0;
                }
            }

            if(gcount >= k){
                left = mid+1;
            }else if(gcount < k){
                right = mid-1;
            }
        }

        System.out.println(right);
    }
}

시간복잡도는 우선 for문으로 보면 n 이고 모든 시험지 총합 log(sum) 만큼 while 문을 돌게 될것이므로 n * log(sum) 으로 보인다