[백준] 2512번 : 예산 - JAVA [자바]

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

---

문제

 

위 문제는 단순하다. 하지만 N의 범위가 10,000일 경우에는 완전 탐색으로 풀었을 경우 1초가 넘어가게 된다. 그래서 완전탐색이 아닌 O(logn)으로 풀 수있는 이분탐색을 활용했다.

 

풀이는 O(nlogn)이다.

 

풀이는 아래와 같이 진행된다.

 

1. 입력값을 받는다.

2. 이분탐색을 위한 배열 정렬을 오름차순으로 진행한다.

3. left, right의 적절한 값을 넣어서 범위를 지정한다.

4. 루프를 돌면서 중간값을 계산하고, 루프 내에서 배열을 완전 탐색해서 mid의 값이 넘어가면 총합에 mid를 더하고, 아니면 배열값 자체를 더한다.

5. 구해진 총합을 M과 비교해서 적절하게 left, right를 조절한다.

6. 루프가 끝나게 되면 right의 값이 답이다.

 

여기서 left의 초기값이 배열중 가장 작은 값이라고 생각하고 넣어서 틀려버렸다....

left의 범위는 0부터 시작한다! 문제를 잘 읽고 범위를 잘 잡아야겠다.. ㅠㅠ

---

전체 코드

public class Main {
	
    public static void main(String[] args) throws Exception {
    	System.setIn(new FileInputStream("./input.txt"));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        StringBuilder sb = null;
        
        int N = Integer.parseInt(in.readLine());
        int[] arr = new int[N];
        
        st = new StringTokenizer(in.readLine());
        
        for(int i = 0; i < N; i++) {
        	int num = Integer.parseInt(st.nextToken());
        	arr[i] = num;
        }
        
        long M = Long.parseLong(in.readLine());
        
        Arrays.sort(arr);
        
        int left = 0;
        int right = arr[N - 1];
        
        while(left <= right) {
        	int mid = (left + right) / 2;
        	long sum = 0;
        	
        	for(int i = 0; i < N; i++) {
        		
        		if(arr[i] <= mid) {
        			sum += arr[i];
        		}
        		else {
        			sum += mid;
        		}
        	}
        	
        	
        	if(sum <= M) {
        		left = mid + 1;
        	}
        	else {
        		right = mid -1;
        	}
        }
        
        System.out.println(right);
    }
}

---

결과