문제

접근

• 먼저 나의 풀이는 다른 사람들의 풀이와 접근 자체가 다르다. 다른 사람들은 이분탐색으로 풀었는데, 다 풀고 다른 사람 풀이를 보니까 이분탐색으로 푸는 것이 더 좋을 것 같다.
• 이분탐색을 이용할 경우 탐색 자체는 O(logn) 수준이지만, 모든 수를 탐색 당 한 번씩 돌아야하기 때문에 O(mlogn)의 시간복잡도를 가진다.
• 나의 풀이는 순차탐색을 기반으로 하고 있기 때문에 O(n)의 시간복잡도를 가진다. 시간복잡도는 나의 풀이가 더 작지만, 이 문제에서는 m보다 n이 더 크기 때문에 실행 결과를 비교해보니 실행시간이 비슷하였다.
• 하지만 나의 풀이는 수학적 연산이 들어가있기 때문에 알고리즘 풀이를 할 때는 범용성이 더 작아보인다 ㅜ
• 나의 풀이를 설명하자면 아래와 같이 비용 관련식을 정리하였고, 계수가 일정한 규칙으로 늘어나는 것을 확인하였다. 그래서 계수에 대해 증감처리를 하여 비용을 구할 때 n번의 연산이 아닌 상수 수준의 연산이 된다.
  

코드

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


public class Main {
    static Map<Long, Integer> map = new HashMap<>();
    static Queue<Long> pq = new PriorityQueue<>();
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        long B = Long.parseLong(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            long n = Long.parseLong(st.nextToken());
            map.put(n, map.getOrDefault(n, 0) + 1);
        }

        for (Long k : map.keySet())
            pq.add(k);
        
        long answer = pq.poll();
        long a = map.get(answer), b = answer * a, c = answer * answer * a;
        while(!pq.isEmpty()) {
            long next = pq.poll();
            long aa = map.get(next);
            long bb = map.get(next) * next;
            long cc = next * next * map.get(next);

            long cost = getCost(a + aa, b + bb, c + cc, next);
            if (cost > B)break;

            a += aa;
            b += bb;
            c += cc;
            answer = next;
            if (cost == B) break;
        }
        while (getCost(a, b, c, answer+1) <= B) answer++;

        System.out.println(answer);
    }

    private static long getCost(long a, long b, long c, long next) {
        return a * next * next - 2 * next * b + c;
    }
}