백준 2512번 BinarySearch

changho Youn·2023년 10월 8일

출처 : 백준 https://www.acmicpc.net/problem/2512

문제 접근 방식

recursive로 해결도 가능하지만, 효율적인 측면에서 가능한 한 최대의 총예산을 찾는 문제이므로, Binary Search를 떠올리게 되었다.
문제를 풀이하는데 있어서, 여러방식으로 풀 수 있지만 시간복잡도 및 효율성을 따지면서 문제 푸는 습관을 들이자.

Binary Search(이진 탐색)이란?

이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.
개념이 그렇게 어렵지않다. 하지만 Binary Search를 이용할 때, 주의할 점은 Data를 정렬한 후에 시행해야 한다는 것이다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Baek2512_2 {
    static int n, m;
    static int[] requestBudget;
    static int optimizeBudget;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        requestBudget = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            requestBudget[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(requestBudget);//very very important
        biSearch();
        System.out.println(optimizeBudget);
    }
    static void biSearch() {
        int start = 0;
        int end = requestBudget[n-1];
        while (start <= end) {
            int mid = (start+end)/2;
            int sum = 0;
            for (int i=0; i<n;i++) {
                if(requestBudget[i]>mid)
                    sum+=mid;
                else sum += requestBudget[i];
            }
            if (sum > m) {
                end = mid - 1;
            } else {
                start=mid+1;
                optimizeBudget = mid;
            }

        }

    }
}