문제 풀이

입력되는 숫자들의 제한이 100만, 10억 등 O($N^2$) O(N) 등으로는 풀기 어려울 것 같아 다른 방법을 먼저 생각해야한다.
이분탐색을 사용해서 푼다면 풀 수 있다.
먼저 팀 목표레벨을 먼저 정하고 그 목표레벨을 달성할 수 있는지 체크를 하고, 팀 목표 레벨의 최대치를 구해주면 된다.

문제 링크

boj/16564

소스코드

PS/16564.java

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


    public class Main {
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        public static void main(String[] args) throws IOException {
            int n,k;
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());
            int [] arr = new int[n];
            for(int i=0;i<n;i++)
            {
                arr[i] = Integer.parseInt(br.readLine());
            }

            Arrays.sort(arr);
            int l = 1, r = 100000000;

            while(l<= r)
            {
                int mid =(l+r)/2;
                long cnt = 0 ;
                for(int i=0;i<n;i++)
                {
                    if(mid > arr[i])
                        cnt += (mid-arr[i]);
                }
                if(cnt > k)
                {
                    r = mid - 1;
                }
                else {
                    l = mid + 1;
                }
            }
            bw.write(Integer.toString(r));
            bw.flush();

        }

    }