[백준] 2512 - 예산 (Java)

[백준] 2512 - 예산 (Java)

문제

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

풀이/후기

이진탐색으로 풀면 된다.

입력을 받을 때 주어진 숫자 중에 가장 큰 값을 max에 넣어준다.

mid값을 조정하면서 이진탐색으로 답을 찾아내면 되는데,

탐색 종료 시 max가 M을 초과하지 않으면서 가능한 최대의 상한액을 나타내므로 max를 출력한다.

코드

package BinarySearch;

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

public class Problem2512 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] num = new int[N];
		StringTokenizer str = new StringTokenizer(br.readLine());

		int min = 0;
		int max = Integer.MIN_VALUE;
		
		for (int i=0; i<N; i++) {
			num[i] = Integer.parseInt(str.nextToken());
			max = Math.max(max, num[i]);
		}
		
		int M = Integer.parseInt(br.readLine());

		
		while (min <= max) {
			int mid = (min + max) / 2;
			
			int sum = 0;
			for (int i=0; i<N; i++) {
				if (num[i] >= mid) sum += mid;
				else sum += num[i];
			}
			
			//System.out.println(sum + " " + mid);
			
			if (sum <= M) {
				min = mid + 1;
			} else {
				max = mid - 1;
			}
		}
		
		System.out.println(max);
		
	}
}

Commit

 

참고