[1주차] 3. 예산

https://yummy0102.tistory.com/303

[JAVA] 백준 2512번 - 예산

---

문제 풀이 및 접근법

먼저 이 문제는 탐색(Search) 문제이다

즉, 데이터들 중에서 특정값을 찾아내는 것이다!

 

가장 간단한 방법으로는 0부터 최대 예산까지 모두 순회하면서 확인하는 것이다

하지만 이는 너무 오래 걸리기 때문에 PASS!

 

문제에서 우리가 찾아야 할 것은 예산의 상한가, 즉 금액이고 예산의 최솟값과 최댓값이 주어진다

그리고 금액 기준으로 보면 0부터 최댓값까지 정렬되어 있는 것과 마찬가지다

따라서 이 문제는 '이분탐색(Binary Search)'을 활용하여 해결할 수 있는 것이다!

이분 탐색은 전체 데이터를 다 확인하지 않고, 범위를 줄여가며 값을 찾는 방식이다

이분 탐색을 사용하기 위한 조건은 데이터가 정렬되어 있어야 한다

 

알고리즘은 다음과 같다

우선 최댓값과 최솟값의 가운데 값을 상한가로 잡고 확인한다

이 때 예산이 남는 경우에는 상한가를 높여서 다시 확인하고, 예산이 모자라면 상한가를 줄여서 다시 확인한다

이를 최솟값과 최댓값이 같을 때까지 반복해준다

 

아래는 코드!

 

 

자바 코드)

public class Step3_3 {
    public int solution(int[] budgets, int M) {
        int min = 0;
        int max = 0;
        for(int b: budgets) {
            if(b > max) {
                max = b;
            }
        }
        int answer = 0;
        while(min<=max) {
            int mid = (min+max)/2;
            int sum = 0;
            for(int b : budgets) {
                if(b>mid) {
                    sum += mid;
                } else {
                    sum += b;
                }
            }
            if(sum <= M) {
                min = mid+1;
                answer = mid;
            } else {
                max = mid - 1;
            }
        }
        return answer;
    }
 }