[백준] 2512 : 예산 (JAVA)

난이도

🥈 2

 

링크

https://www.acmicpc.net/problem/2512

2512번: 예산

---

문제

---

풀이과정

해당 문제도 이분탐색을 사용해서 푸는 문제이다.

 

이분탐색에 대해서는 아래 글에서 작성해두었으니 참고하면 좋을거 같다!

(풀이 설명도 아래의 글을 참고하면 될 것 같다.)

https://amepistheo.tistory.com/4

[백준] 2110 : 공유기 설치 (JAVA)

 

정해진 총액 이하에서 가능한 한 최대의 총 예산(by 정수 상한액)을 출력하는 문제였기 때문에

이번에도 Upper Bound를 사용하면 되는 문제였다. 

 

1) 최소 예산이 1이었기 때문에 left = 1로 설정

2) 최대 예산은 입력값의 최댓값인 right = money[N-1]로 설정

3) for문을 돌며 정수 상한액에 따른 총 예산 계산

4) 최종적으로 계산된 총 예산을 확인

 

계산된 총 예산과 주어진 총 예산을 비교하여

• 계산된 총 예산 > 주어진 총 예산
  : 정수 상한액이 크게 잡혀있음 → 정수상한액 줄임
• 계산된 총 예산 < 주어진 총 예산
  : 정수 상한액이 작게 잡혀있음 → 정수상한액 늘림
• 계산된 총 예산  = 주어진 총 예산
  : 만족하는 정수상한액들 중 최댓값를 모름! → 정수상한액 늘림

➡️ 이 부분이 위 링크에 있는 문제와의 차이점인데

       계산된 총 예산이 넘칠 때! 정수상한액을 줄여줘야 되고,

       계산된 총 예산이 작거나 같을 때! 정수상한액을 늘려줘야하기 때문에

       if문의 조건이 다르다는 걸 잘 알아둬야 한다!

 

 

Upper Bound (원하는 값 k를 초과한 값이 처음 나오는 위치를 찾는 과정')를 사용하여

위의 문제에서는 '가능한 한 최대의 총 예산'이 되도록하는 예산들 중 최댓값을 구해야하고, 

 

left가 가장 마지막에 바뀐 값 (while문을 빠져나가는 조건이 left > right이기 때문)이므로 left - 1을 출력하면 된다.

 

🚨 이분탐색을 하기 전에 꼭! 정렬하는거 잊지 말기..

---

전체 코드

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

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

        int N = Integer.parseInt(br.readLine());

        int[] money = new int[N];

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            money[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(money);

        int M = Integer.parseInt(br.readLine());

        int left = 1;
        int right = money[N-1];

        while (left <= right) {
            int mid = (left + right) / 2;

            int count = 0;

            for (int i = 0; i < N; i++) {
                if (money[i] < mid) {
                    count += money[i];
                }
                else {
                    count += mid;
                }
            }

            if (count > M) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }

        System.out.println(left - 1);
    }
}

 

결과