BOJ_2512 : 예산

👉 문제링크

2512번: 예산

---

---

🔸 문제 분석 🔸

• n개의 숫자의 합이 m보다 작거나 같게 만들어야 한다. 그 중 최대값을 출력한다.
  • 숫자들의 합이 m보다 작다면, 기존 숫자들 중 최대값을 출력한다.
  • 숫자들의 합이 m보다 크다면, 최대값 커트라인을 만들고 합이 최대가 될 때의 커트라인을 출력한다.

🔸 코드 🔸

import java.util.Scanner;

public class Main {
    private static int sum(int[] arr, int max) {
        int sum = 0;
        for (int i : arr) {
            if (i > max){
                sum += max;
            }
            else sum += i;
        }
        return sum;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int m = sc.nextInt();

        if (sum(arr, 100_000) <= m) {
            int max = 0;
            for (int i : arr) {
                if (i > max)
                    max = i;
            }
            System.out.println(max);
        }
        else {
            int l = 1, r = 100_000, mid = -1;
            while (l <= r) {
                mid = (l+r)/2;
                int sum = sum(arr, mid);
                if (sum <= m)
                    l = mid + 1;
                else
                    r = mid - 1;
            }
            System.out.println(r);
        }
    }
}

🔸 코드 해석 🔸

• 배열의 합을 반환하는 sum 메소드는 배열과 커트라인을 입력받아 합을 출력한다.
• 배열의 합이 m보다 작다면, 기존 숫자들 중 최대값을 출력한다.
• 배열의 합이 m보다 크다면, 이분탐색을 통해 합이 m보다 작은 최대값이 될 때의 커트라인을 찾는다. 

---

🔸 end 🔸

• 오랜만에 이분탐색을 사용하려니 많이 어려웠던 것 같다.
• 문제에서 이분탐색을 어떻게 활용해야하는지는 잘 캐치해서 풀이했는데, 탐색 종료조건을 잘 정하지 못해서 2번 틀리게 되었다.
  • 특히 최종으로 mid를 출력하는게 아니라 r을 출력해야했다.