<stdio.han>

[문제 링크]

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

[난이도]

- Silver 1

[알고리즘]

- 매개변수 탐색

[코드]

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

public class Main {
    static int N, M, left, right = 0, result = 0;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            right += arr[i];
            left = Math.max(left, arr[i]);
        }

        parametricSearch();
        System.out.println(result);
    }
    static void parametricSearch() {
        while (left <= right) {
            int mid = (left + right) / 2;

            int sum = mid;
            int count = 0;
            if (M >= getMid(mid)) { // 인출한 횟수가 작거나 같으면 mid를 줄여야 한다
                result = mid;
                right = mid - 1;
            } else { // 인출한 횟수가 M보다 클 경우 mid를 늘려야 한다
                left = mid + 1;
            }
        }
    }

    static int getMid(int tmp) {
        //tmp = 한번에 인출할 수 있는 돈
        int count = 1; // 돈을 인출한 횟수
        int money = tmp; // 현재 남아있는 돈

        for (int num : arr) { // 하루에 사용할 금액 num
            money -= num; // 현재 남아있는 돈에서 사용할 금액을 뺀다
            if (money < 0) { // 0원보다 적어지면 다시 현금을 인출한다.
                count++; // 현금을 인출했으므로 count++
                money = tmp - num; // 0원보다 적어질 경우 남은 금액을 통장에 넣고 다시 인출하므로
            }
        }
        return count; // 인출한 횟수 리턴
    }
}

[풀이]

입력값을 정렬해서 푸는게 아니므로 이분탐색이 아닌 매개변수 탐색이다.

입력받은 arr배열을 돌면서 현재 보유한 돈에서 사용할 금액을 빼며 계산해준다. 현재 보유한 돈이 0보다 적어질 경우 남아있는 돈을 통장에서 넣고 인출하므로 count++ 해준다.

        for (int num : arr) { // 하루에 사용할 금액 num
            money -= num; // 현재 남아있는 돈에서 사용할 금액을 뺀다
            if (money < 0) { // 0원보다 적어지면 다시 현금을 인출한다.
                count++; // 현금을 인출했으므로 count++
                money = tmp - num; // 0원보다 적어질 경우 남은 금액을 통장에 넣고 다시 인출하므로
            }
        }

https://www.acmicpc.net/problem/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);
            }