[백준 2512번][Java] 예산 - 이분 탐색 종결 조건

www.acmicpc.net/problem/2512

2512번: 예산

 

이분 탐색시 종결 조건에 대해서 정리하려고 합니다.

 

우선 위의 상황을 간단하게 설명하겠습니다.

우리는 이 문제와 같이 어떤 특정 값(max)에 최대한 근접하는 최대값을 찾고 싶습니다. 위 사진은 이분 탐색을 통해 범위를 2개까지 좁힌 상태이고 a < max < b 이므로 답은 a가 나와야 합니다. 

범위를 이분하는 방식은 (low + high)/2 에서 계산한 값을 기준으로 max보다 클 경우 왼쪽 범위, 작을 경우 오른쪽 범위를 선택하도록 합니다. 

 

이제 본론으로 들어가겠습니다.

1번 종결 조건에서는 답을 제대로 찾지 못하는 경우가 생깁니다. 범위의 길이가 2일때 mid는 low를 가리키게 되는데 현재 low에 해당하는 값 a는 max보다 작으므로 오른쪽 범위 b를 선택합니다. 결국 b가 반환되게 되는데 이 값은 max보다 크기 때문에 오답입니다.

 

물론 약간 수정하면 답을 찾을 수 있습니다. 종결 조건(low == high)에서 계산한 값이 max를 넘는 경우 low-1 나 high-1을 반환함으로서 해결 가능합니다. 요소가 두 개까지 좁혀진 경우 반드시 max 값은 a와 b 사이에 있기 때문입니다.

 

이런 문제는 값 중에 정확히 max에 해당하는 값이 존재하지 않을 경우 발생합니다.  

 

2번 종결 조건의 경우는 범위가 하나로 좁혀진 경우 (low == high)인 경우에도 이분하는 작업을 하게 됩니다. 정확히 max값을 찾지 못하는 경우 결국 low > high가 되게 되는데 이것 때문에 재밌는 상황이 연출됩니다.

이 종결 조건에서도 (low + high)/2값은 동일하기 때문하기 때문에 결국 b구간(high , high)을 선택하게 됩니다. 하지만 아직 종결 조건을 충족시키지 못했죠. 값 b는 max보다 크기 때문에 왼쪽 구간을 선택하려고 구간을 수정합니다.

결국 구간은 (high, high) => (high, low)가 됩니다.  이 상태에서 (low + high)/2는 low를 가리키므로 정답이 됩니다.

 

 

 

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

/*
예산
https://www.acmicpc.net/problem/2512
*/
public class Main {
	static int n;
	static long m;
	static List<Integer> budgetRequests;
	public static void main(String[] args) throws IOException {
		InputReader reader = new InputReader("testcase.txt");
//		InputReader reader = new InputReader();
		n = reader.readInt();

		budgetRequests = new ArrayList<>();
		StringTokenizer st = new StringTokenizer(reader.readLine());
		for (int i = 0; i < n; i++) {
			budgetRequests.add(Integer.parseInt(st.nextToken()));
		}
		budgetRequests.sort(Comparator.naturalOrder());
		m = reader.readLong();
//		System.out.println(budgetRequests);

//		int max = getMaxBudget();
		int max = getMaxBudget2(0, budgetRequests.get(budgetRequests.size()-1));
		System.out.println(max);

	}
	//재귀 버전
	private static int getMaxBudget2(int low, int high) {
		//종결 조건
		int mid = (low + high)/2;
		if(high < low) {
			return mid;
		}

		long totalBudget = getTotalBudget(mid);
//		System.out.format("low : %d, high : %d, totalBudget : %d, mid : %d\n", low, high, totalBudget, mid);
		if(totalBudget > m) return getMaxBudget2(low, mid-1);
		else if(totalBudget < m) return getMaxBudget2(mid+1, high);
		else return mid;
	}

	//while문으로 이분 탐색
	private static int getMaxBudget() {
		int low = 0; int high = budgetRequests.get(budgetRequests.size()-1);
		int mid = (low + high)/2;
		while(low <= high) {
			long totalBudget = getTotalBudget(mid);

			if(totalBudget > m) high = mid-1;
			else if(totalBudget < m) low = mid+1;
			else return mid;

			mid = (low + high)/2;
//			System.out.format("low : %d, high : %d, totalBudget : %d, mid : %d\n", low, high, totalBudget, mid);
		}
		return mid;
	}



	private static long getTotalBudget(int budget) {
		long sum = 0;
		for (int i = 0; i < n; i++) {
			int budgetRequest = budgetRequests.get(i);
			if(budgetRequest <= budget) {
				sum += budgetRequest; continue;
			}
			sum += budget * (n-i); break;
		}
		return sum;
	}
}

class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public List<Character> readLineIntoCharList() throws IOException {
		List<Character> l = new ArrayList<>();
		while(true) {
			int readVal = br.read();
			if(readVal == '\n' || readVal == -1) break;
			l.add((char)readVal);
		}
		return l;
	}

	public boolean ready() throws IOException {
		return br.ready();
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}