백준 2512번: 예산[JAVA]

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

2512번: 예산

 

 

[정답 코드]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken()); // 지방의 수
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine(), " "); // 각 지방의 예산요청
        int left = 0;
        int right = -1; // 예산의 최대 금액
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            right = Math.max(right, arr[i]);
        }
        int M = Integer.parseInt(br.readLine()); // 총 예산
        while (left <= right) {
            int mid = (left + right) / 2;
            long budget = 0;
            for (int i = 0; i < N; i++) {
                budget += Math.min(arr[i], mid);
            }
            if (budget <= M) {
                left = mid + 1;
            } else {
                right = mid -1;
            }
        }
        System.out.println(right);
    }
}

 

[설명]

이 문제는 이분탐색, 매개변수 탐색(파라매트릭 서치)을 활용하는 문제이다. 그 중에 매개변수 탐색을 활용했다. 나는 이분탐색, 매개변수 탐색문제를 풀어본적이없어서 어떻게 접근해야할지 막막해 다른사람이 작성한 글을 참고했다.

매개변수탐색은 주어진 범위 내에서 원하는 값 또는 조건에 일치하는 값을 찾아내는 알고리즘이다.

범위는 left 와right로 왼쪽 끝 값과 오른쪽 끝 값을 설정하고 그 범위의 중간값을 계속 찾아내며 조건을 찾아내는 방법이다.

문제를 예로들면 문제의 정답은 127인데 해당 조건을 향해 left 와 right 값을 조정해 나아가는것이다. 처음 left 값은 0 right 값은 150으므로 mid는 75이다. 

반복문을 1회 더 시행하면

이런식으로 left 76, mid 113, right 150 이다. 1회 더 실시하면

left 114, mid 132, right 150 이다.

이런식으로 mid가 해당조건을 넘어서지 못하면 left를 mid + 1로 변경하고 해당조건을 넘어가버리면 right를 mid -1로 설정해나아가면 범위를 좁히는 것이다. 이 문제에서 중요한 점은 해당 지방마다 예산의 한도가 정해져 있기때문에 각 지방의 예산 한도를 넘어서지 않게 주의해야한다. 아래 코드처럼 mid가 해당 지방의 예산보다 작을경우에는 mid를 budget에 추가해주고 지방의 예산을 넘어설 경우에는 해당 지방의 최대예산을 추가해준다.

            for (int i = 0; i < N; i++) {
                budget += Math.min(arr[i], mid);
            }