[Baekjoon] 백준 알고리즘: 2512 - 예산

문제

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

 

 

input:

output:

첫번째 나의 풀이

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main T = new Main();

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        sc.nextLine();

        int[] arr = new int[n];

        String s = sc.nextLine();
        String[] strings = s.split(" ");
        for(int i = 0; i < strings.length; i++){
            arr[i] = Integer.parseInt(strings[i]);
        }

        long m = sc.nextLong();

        T.solution(n, m, arr);

    }

    public void solution(int n, long m, int[] arr) {

        Arrays.sort(arr); // 정렬

        int lt = arr[0];
        int rt = arr[n - 1];
        long max = 0;

        while (lt <= rt){
            int mid = (lt + rt) / 2;
            int sum = 0;

            for(int i = 0; i < arr.length; i++){
                if(arr[i] > mid){
                    sum += mid;
                } else {
                    sum += arr[i];
                }
            }

            // 반복문의 합이 m보다 클 경우
            if(sum > m){
                rt = mid - 1;
            } else { // 1씩 증가하기
                max = Math.max(max, mid); // mid가 가능한 최대값일 수 있음
                lt = mid + 1;
            }
        }

        System.out.println(max);
    }
}

내가 생각했던 풀이과정

대표 알고리즘: 이분 탐색(UpperBound)

결과: X

틀린 이유: 예산에서의 제시된 값보다 제일 적을 수 있었다 이를 위해 lt = arr[0] → lt = 0 으로 수정

두번째 나의 풀이

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main T = new Main();

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        sc.nextLine();

        int[] arr = new int[n];

        String s = sc.nextLine();
        String[] strings = s.split(" ");
        for(int i = 0; i < strings.length; i++){
            arr[i] = Integer.parseInt(strings[i]);
        }

        long m = sc.nextLong();

        T.solution(n, m, arr);

    }

    public void solution(int n, long m, int[] arr) {

        Arrays.sort(arr); // 정렬

        int lt = 0;
        int rt = arr[n - 1];
        long max = 0;

        while (lt <= rt){
            int mid = (lt + rt) / 2;
            int sum = 0;

            for(int i = 0; i < arr.length; i++){
                if(arr[i] > mid){
                    sum += mid;
                } else {
                    sum += arr[i];
                }
            }

            // 반복문의 합이 m보다 클 경우
            if(sum > m){
                rt = mid - 1;
            } else { // 1씩 증가하기
                max = Math.max(max, mid); // mid가 가능한 최대값일 수 있음
                lt = mid + 1;
            }
        }

        System.out.println(max);
    }
}

내가 생각했던 풀이과정

대표 알고리즘: 이분 탐색(UpperBound)

1. 이분 탐색을 위해 정렬
2. 이분 탐색을 위해 중간 값 설정
   1. 중간 값을 설정할 때는 인덱스 값이 아닌 정수값으로 설정
3. upperBound를 해야하기 떄문에 max값을 세팅
4. 배열의 반복문만큼 합을 구한다
   1. mid의 값보다 배열의 값이 클경우
      1. mid값을 더한다
   2. mid의 값보다 배열의 값이 같거나 작을 경우
      1. 배열의 값을 더한다
5. 반복문의 합처리
   1. 반복문의 합이 최댓값보다 클경우
      1. rt의 값을 -1
   2. 반복문의 합이 최솟값보다 작을 경우
      1. max 값을 세팅
      2. lt 값 수정

결과: O