[BOJ/Java] - 흩날리는 시험지 속에서 내 평점이 느껴진거야

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

 

이진탐색을 이용해서 그룹 당 문제개수의 합의 최소를 구하는 문제

이진탐색을 사용해서 푸는 것이란 것을 몰르고 풀었다면, 이걸 이진탐색을 사용하겠다는 생각이 들었을까 .. 싶었던 문제였다.

 

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

public class Main {

    static int arr[];
    static int N;
    static int M;


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

        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st=new StringTokenizer(br.readLine());

        N=Integer.parseInt(st.nextToken());
        M=Integer.parseInt(st.nextToken());
        st=new StringTokenizer(br.readLine());
        arr=new int[N];

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

        }

        bw.write(String.valueOf(BinarySearch(0,2000000)));


        br.close();
        bw.flush();
        bw.close();

    }

    static int BinarySearch(int left,int right){
        int result=0;
          //그룹의 수를 새주는 변수

        while(left<=right){
            int mid=(left+right)/2;
            int sum=0;
            int gnt=0;
            for(int i=0;i<N;i++){
                sum+=arr[i];
                if(sum>=mid){
                    gnt++;
                    sum=0;
                }

            }
            if(gnt>=M){
                left=mid+1;
                result=mid;
            }
            else if(gnt<M){
                right=mid-1;
            }


        }
        return result;


    }


}

 

배열에 입력 값들을 받은 다음 

기본 이진탐색 코드안에

반복문으로 배열안에 있는 값들을 더하다가 (sum)  sum이 mid값보다 크거나 같을 경우,

예를들어 만약 50이 mid값이었다면 51이 되었을때 그룹카운트를 하나 늘려준다.

mid값으로 비교하는 것이 포인트다

이런식으로 배열의 값들을 sum변수에 더하면서 mid값보다 크거나 같을경우 그룹카운트를 늘려주는 식으로 진행하는데,

처음에 입력받은 목표 그룹수 보다  그룹카운트가 작다면, 비교대상으로 삼은 mid값이 너무 컸다는 것을 의미하므로

mid값을 줄여야한다. 

그러므로 right값을 mid-1로 바꾸고 다시 이진탐색을 한다.

만약에 그룹카운트가 목표 그룹수보다 크다면,  mid값이 작았다는 것을 의미하므로 

left값을 mid+1로 바꿔준다.

만약에 그룹카운트가 같을 경우에는, (우리의 목표 그룹수와 카운트된 그룹수가 같을경우에는)

우리가 원하는 값이 나왔으므로 비교했던 mid값이 맞은 것이니 result에 저장한다. 

그러나 이 mid값이  최대값이라고 보장을 해주지 못한다. ( 왜냐하면 44로도 두그룹을 나눌 수있고, 50으로도 두 그룹을 나눌 수 있다면,

우리는 50을 선택해야하기 때문에)

그러므로 mid값을 늘려서 수행한다. 

(이유:  그룹안에 합들과 mid값을 비교해서 그룹 수를 측정하는 것이므로 mid값을 늘리는 작업을 해야 그룹안에 합이 최댓값에 가까워질것이다.)

결국 이진탐색종료조건에 도달하게될것이고, 그때의 result값이  원하는 값이 될것이다.