[백준] 2512번 : 예산

예산

---

풀이 방법

오늘도 여전히 뻘짓을 한 번 했다.. ㅎㅎ
문제 해결 방법먼저 설명해보자면, 순서가 중요하지 않기 때문에 정렬을 해서 푸는게 유리하다.

내가 아는 지식으로 봤을 때 정렬이 되있는 경우라면 이분탐색 알고리즘을 사용하는게 가장 적합하다고 생각했다.

풀이는 굉장히 간단하다~

여튼 이번에 한 뻘짓을 얘기해보자면,
입력 - M은 N 이상 1,000,000,000 이하이다. 라고 나와있어서
큰 생각없이 left값을 N부터 시작했다.

하지만, 이 값은 단지 입력으로 들어온다는 값인데, 예산의 범위를 한정지어 버렸다.
반례를 들어보자면

5
100 100 100 100 100
10

이의 답은 2 이다.
즉, 총 예산의 값과 관계없는데 헛짓거리를 해버렸당..
그래도 어느 알고리즘을 써야할지 짧은 시간에 선택해서 구현했던 것 같다.
조금만 더 디테일을 신경써주는 것을 목표로하자..!

코드

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

        int n = Integer.parseInt(br.readLine());
        int[] budget = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<n;i++) {
            budget[i] = Integer.parseInt(st.nextToken());
        }
        int m = Integer.parseInt(br.readLine());

        Arrays.sort(budget);

        if(Arrays.stream(budget).sum() < m) {
            System.out.println(budget[n-1]);
            return;
        }

        int left = 1;
        int right = budget[n-1];
        int boundary = 0;
        while(left <= right) {
            int mid = (left + right) / 2;

            // 정수 상한액을 기준으로 비교해서 계산
            int sum = 0;
            for(int i=0;i<n;i++) {
                if(budget[i] < mid)
                    sum += budget[i];
                else
                    sum += mid;
            }

            if(sum <= m) {
                boundary = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        System.out.println(boundary);
    }
}