[백준/JAVA] 2512번: 예산

🔺 문제

2512번: 예산

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
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[] A = new int[N];
 
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        int M = Integer.parseInt(br.readLine());
        
        // 이분 탐색
        Arrays.sort(A);
        
        int left  = 0;
        int right = A[N - 1];
        
        while(left <= right) {
            int mid = (left + right) / 2;   // 내야 할 세금
            long budget = 0;                // 모든 지방 세금의 합
            
            for(int i = 0 ; i < N ; i++) {
                if(A[i] < mid) budget += A[i];
                else           budget += mid;
            }
            
            if(budget <= M) { // 예산이 아직 총량에 도달하지 못 한 경우
                left = mid + 1;
            }
            else { // 예산이 초과된 경우
                right = mid - 1;
            }
        }
        
        System.out.println(right);
    }
}

✅ 해결 아이디어
✔ 이분 탐색
- left ~ right 범위 내에서 탐색을 통해 특정 수 찾기.

 

---

🔺 다른 풀이들

- 다들 비슷하심

 

---

💬 느낀 점

순서 흐름을 잘 생각하고 코드를 작성해보자....

초장에 while문 안에서 for문이랑 if문 순서 바꿔서 생각해버렸음....ㅠ

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

백준 2512번 : 예산 (Java)

 

[Java] 백준 2512번

 

[알고리즘] 백준 2512 예산 -이분탐색- 자바