백준 2512 - 예산

Java

2512 번 - 예산

문제

접근 방법

단순하게 반복문으로 해결이 가능하지만, 이분 탐색을 사용하여 시간을 단축하는 문제이다.

반복문으로 해결 할 시, 상한액을 1부터 예산 최대까지 기준값이 예산 내에 충족하는지 확인한다.
따라서 시간 복잡도는 예산 중 최대액을 k라고 할 시, O(n * k) 이며, O(n^2) 이다.

이진 탐색을 사용 할 시, 1부터 예산 최대까지 탐색을 단축 할 수 있다.
시간 복잡도는 O(n * log(k)) 이며, O(nlogn) 이다.

코드

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

public class Main {
	static int n, result, m, biggest;
	static int[] arr;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());

    	arr = new int[n];
    	stk = new StringTokenizer(br.readLine());
    	for(int i = 0; i < n; i++) {
    		arr[i] = stoi(stk.nextToken());
    		biggest = Math.max(arr[i], biggest);
    	}
    	m = stoi(br.readLine());

    	// 이분탐색 시작
    	binarySearch(1, biggest);

		/* 단순 반복문으로 해결
		for(int i = 1; i <= biggest; i++) {
    		if(cal(i) == 0) {
    			result = i;
    		}
    	}
		*/

    	System.out.println(result);
    	br.close();
	}

	private static void binarySearch(int low, int high) {

		int mid;
		if(low <= high) {
			mid = (low + high) / 2;

			int rt = cal(mid);
			// 예산 분배시, 분배 금액이 예산 내에 들어오면
			if(rt == 0) {
				result = mid;
				// 기준을 올린다.
				binarySearch(mid + 1, high);

			}
			// 예산이 더 크면, 기준을 내린다.
			else if(rt == 1) {
				binarySearch(low, mid - 1);
			}
		}

	}

	private static int cal(int curN) {

		int sum = 0;
		for(int i = 0; i < n; i++) {
			if(arr[i] <= curN) {
				sum += arr[i];
			}
			else {
				sum += curN;
			}
		}
		// 예산 분배시, 분배 금액이 예산 내에 들어오면
		if(sum <= m) {
			return 0;
		}
		// 분배 금액이 예산보다 클 시, 기준을 낮춘다.
		else {
			return 1;
		}
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}