백준 2512번 예산 (JAVA)

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

2512번: 예산

 

저는 이분탐색으로 문제를 해결하였습니다.

각각의 가격에 대해 되는지 안되는지를 확인하게 된다면 n*m으로 시간초과가 나올 것입니다. 그래서 이분탐색으로 log(n)*m의 시간복잡도로 낮추어 문제를 해결하였습니다.

 

package BOJ.binarysearch;

import java.awt.print.Pageable;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_2512 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] price = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        int max = 0;
        for(int i = 0 ; i < n ; i++){
            price[i] = Integer.parseInt(st.nextToken());
            max = Math.max(price[i],max);
        }
        int m = Integer.parseInt(br.readLine());
        int result = cal(price,max,m);
        System.out.println(result);
    }

    private static int cal(int[] price,int max ,int m) {
        int start = 1;
        int end = max;
        int result = 0;
        while(start <= end) {
            int mid = (start+end)/2;
            if(checkPrice(price,mid,m)){
                result = mid;
                start = mid + 1;
            }else{
                end = mid - 1;
            }
        }
        return result;
    }

    private static boolean checkPrice(int[] price, int mid,int m) {
        int sum = 0;
        for(int num : price){
            sum += Math.min(num,mid);
        }
        if(sum <= m){
            return true;
        }else{
            return false;
        }
    }
}