[BOJ] 2343. 기타 레슨

이분 탐색을 사용하는 문제이다.

최소값을 찾는것에 이분탐색을 사용하는것이 좋을것이라 생각했는데, 이분탐색의 다음조건을 넘어가는 check함수를 구현함에 있어서 고민을 많이했다. 맨처음엔 단순하게 arr를 M개로 쪼개는 모든 경우의 수를 생각하였는데, N이 최대 100,000이여서 최악의 경우 이분탐색을 사용하더라도 check함수로 인한 시간초과가 발생할 수 있다고 생각하였다. 그래서 단순하게 현재검증해야하는 값(mid)으로 arr를 나눈다면 몇조각이 나오는지 확인하였고, 그것을 M과 비교하여 M이하면 참, 초과면 거짓을 반환하는 check함수를 만들어 사용하였다. 이 check함수에선 또 하나 체크해야 할 것이 있는데 만일 mid값이 arr의 원소보다 작다면 무조건 거짓을 반환하는 조건을 추가하는 것이다.

간단한 방법이 있지만 너무 어렵게 생각했던 문제인것 같다.

package study4;
 
import java.awt.Checkbox;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_2343_기타레슨 {
    static int N,M;
    static int[] arr;
    static int totalSum;
    static int answer;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N=Integer.parseInt(st.nextToken());
        M=Integer.parseInt(st.nextToken());
        
        arr=new int[N];
        totalSum=0;
        answer=Integer.MAX_VALUE;
        st=new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++) {
            arr[i]=Integer.parseInt(st.nextToken());
            totalSum+=arr[i];
        }
        
        binary();
        
        System.out.println(answer);
        
    }
    static void binary() {
        int left=1;
        int right=totalSum;
        
        
        while(left<=right) {
            
            int mid=(left+right)/2;
//            System.out.println(mid);
            boolean check = calc(mid);
            
            if(check==true) {
                answer=Math.min(answer, mid);
                right=mid-1;
            }else {
                left=mid+1;
            }
        }
    }
    
    static boolean calc(int value) {
        int count=1;
        int tempSum=0;
        
        for(int i=0;i<N;i++) {
            if(arr[i]>value)
                return false;
            
            if(tempSum+arr[i]<=value) {
                tempSum+=arr[i];
            }else {
                count+=1;
                tempSum=arr[i];
            }
        }
        
        if(count<=M)
            return true;
        else
            return false;
    }
}