특정 조건의 값(배열에 없는, 선택할 떄?) - 이진탐색

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

class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)) ;
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        String [] Strarr = br.readLine().split(" ");
        int[] Narr = new int[N];
        int sumNarr = 0 ;
        for(int i =0; i<N; i++)
            {
                Narr[i] = Integer.parseInt(Strarr[i]);
                sumNarr+=Narr[i];    
            }
        Arrays.sort(Narr);
        int M = Integer.parseInt(br.readLine());

        if(sumNarr<M)
        {
            bw.write(String.valueOf(Narr[N-1]));
            bw.flush();
            bw.close();
        }

        else{
            int start = 0 ;
            int end = Narr[N-1];
            int result = 0 ;
            int sumcnt = 0 ;

            while(start<=end)
                {
                    int mid = (start+end)/2;
                    sumcnt = 0;
                    //탐색 범위 설정
                    for(int val: Narr) 
                        {
                            if(val<mid)
                            {
                                sumcnt+=val;
                            } else{
                                sumcnt+=mid;
                            }
                        }

                    if (sumcnt>M) //판별에 따른 탐색 범위 설정                        
                    {
                        end =mid-1; 
                    } else {
                        result = mid;
                        start = mid +1;
                    }
                }

            bw.write(String.valueOf(result));
            bw.flush();
            bw.close();
            
        }
        

    }
    
}

 

1. 이진 탐색
(일단 정렬 -> 조건에 따라 start ,end를 정해주고 mid 값을 도출)

2. start ,end를 재조정할 기준을 계산

3. start, end재조정에 따라서 mid 값 계산 후 특정 범위 (start =mid+1 or end = mid-1)

 

핵심은, 배열에 없는 특정 값에 따른 계산이 필요할 때 .