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

백준 2512 실버2 예산

위 문제를 보고 어떻게 구할 수 있을까 하다가 직접 내 머리대로 로직을 생각해보았다.
우선 입력 받은 것들을 정렬하고
일단 다 더해서 총 합이 총 액을 넘으면 입력 배열 인덱스를 하나씩 바꿔 총 합이 총 액을 넘지 않게 한 다음
거기서 1씩 더해 총 액을 넘기 바로 전이 상한값이다 라는 로직을 생각해냈었다.

예제 답은 잘 나왔지만
하지만 메모리 초과가 나게 되고
위 로직은 그냥 예제의 크지 않은 숫자만 보고 문제를 제대로 안읽고 생각했다는 것을 알게되었다 ㅠㅠ

---

메모리 초과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bufferedReader.readLine()); //지방의 수
        String str = bufferedReader.readLine(); // 각 지방 예산 요청
        Integer arr[] = new Integer[N];

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(str.split(" ")[i]);
        }

        int M = Integer.parseInt(bufferedReader.readLine()); //총 예산

        Arrays.sort(arr, Collections.reverseOrder()); //int arr는 에러남. Integer arr
        HashMap<String, Integer> map = new HashMap();

        int sum, pointer = 0, num = 1;
        boolean flag = false;
        while (true) {
            sum = 0;
            for (int i = 0; i < N; i++) {
                sum += arr[i];
            }
            if (M < sum) {
                for (int j = 0; j <= pointer; j++) {
                    arr[j] = arr[num];
                }
            } else {
                map.put("max", arr[0]);
                flag = true;
                break;
            }
            num++;
            pointer++;
        }
        if (!flag) {
            while (M > sum) {
                map.put("max", arr[0]);
                sum = 0;
                for (int k = 0; k < N; k++) {
                    if (k < pointer) {
                        arr[k] = ++arr[k];
                    }
                    sum += arr[k];
                }
            }
        }

        System.out.println(map.get("max"));
    }
}

---

아무리 봐도 map도 쓰고 이것저것 자료구조를 많이 써서 메모리 초과가 났다고 생각했다.
그래서 없애고 문제 유형을 찾아보니 이분탐색이었다.

이분탐색 문제만 만나면 나의 반응
"이게 이분 탐색이라고?"

이분탐색 문제 예측을 못하겠다ㅠ
이분탐색인 것을 알고 난 후에는 그래도 쉽게 수정해서 예제 답까지 출력은 되었다 :D
하지만 또 메모리 초과가 나게 되고...

---

메모리 초과2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bufferedReader.readLine()); //지방의 수
        String str = bufferedReader.readLine(); // 각 지방 예산 요청
        int arr[] = new int[N];
        
        int sum = 0;
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(str.split(" ")[i]);
            sum += arr[i];
        }

        int M = Integer.parseInt(bufferedReader.readLine()); //총 예산

        Arrays.sort(arr); //int arr는 에러남. Integer arr

        if(M < sum){
            // 상한가 결정이 필요한 경우 - 이분탐색
            int start = M / N;
            int end = arr[N-1]-1;
            int mid;
            int max = 0;

            while(start <= end){
                sum = 0;
                mid = (start + end) / 2;
                for(int i=0;i<N;i++){
                    if(arr[i] > mid){
                        sum += mid;
                    } else{
                        sum += arr[i];
                    }
                }
                if(sum < M){
                    max = Math.max(max, mid);
                    start = mid + 1;
                } else{
                    end = mid - 1;
                }
            }
            System.out.println(max);

        } else{
            // 상한가 결정 필요 없는 경우
            System.out.println(arr[N-1]);
        }
    }
}

---

왜 메모리 초과가 났을까?
설마 입력을 StringTokenizer으로도 해야되려나?
그래서 수정하고 다시 해봤다.

---

틀렸습니다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bufferedReader.readLine()); //지방의 수
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine()); // 각 지방 예산 요청
        int arr[] = new int[N];
        
        int sum = 0;
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(stringTokenizer.nextToken());
            sum += arr[i];
        }

        int M = Integer.parseInt(bufferedReader.readLine()); //총 예산

        Arrays.sort(arr); //int arr는 에러남. Integer arr

        if(M < sum){
            // 상한가 결정이 필요한 경우 - 이분탐색
            int start = M / N;
            int end = arr[N-1]-1;
            int mid;
            int max = 0;

            while(start <= end){
                sum = 0;
                mid = (start + end) / 2;
                for(int i=0;i<N;i++){
                    if(arr[i] > mid){
                        sum += mid;
                    } else{
                        sum += arr[i];
                    }
                }
                if(sum < M){
                    max = Math.max(max, mid);
                    start = mid + 1;
                } else{
                    end = mid - 1;
                }
            }
            System.out.println(max);

        } else{
            // 상한가 결정 필요 없는 경우
            System.out.println(arr[N-1]);
        }
    }
}

---

입력을 StringTokenizer로 하니까 메모리 초과는 안났는데 틀렸습니다가 나왔다.

위 코드가 왜 틀렸나 싶었는데 반례가 있었다.

5
100 100 100 100 100
10
답: 2

찾아보니 sum < M이 아니라 sum < = M으로 해야 됐던 것.

---

성공

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bufferedReader.readLine()); //지방의 수
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine()); // 각 지방 예산 요청
        int arr[] = new int[N];

        int sum = 0;
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(stringTokenizer.nextToken());
            sum += arr[i];
        }

        int M = Integer.parseInt(bufferedReader.readLine()); //총 예산

        Arrays.sort(arr); //int arr는 에러남. Integer arr

        if(M < sum){
            // 상한가 결정이 필요한 경우 - 이분탐색
            int start = M / N;
            int end = arr[N-1]-1;
            int mid;
            int max = 0;

            while(start <= end){
                sum = 0;
                mid = (start + end) / 2;
                for(int i=0;i<N;i++){
                    if(arr[i] > mid){
                        sum += mid;
                    } else{
                        sum += arr[i];
                    }
                }
                if(sum <= M){
                    max = Math.max(max, mid);
                    start = mid + 1;
                } else{
                    end = mid - 1;
                }
            }
            System.out.println(max);

        } else{
            // 상한가 결정 필요 없는 경우
            System.out.println(arr[N-1]);
        }
    }
}