백준 2512(JAVA) - 예산

2512번: 예산 (acmicpc.net)

2512번: 예산

 

오늘의 문제는 실버3 예산문제이다. 분명 실버5~브론즈 문제정도를 출제하자고 합의를 보았는데... 대체 누군지 모르겠지만 갑자기 실버3 문제를 내었다. 예산 문제를 푸는데 처음에 어떻게 하면 좋을까 생각하다가 탐색 기법을 사용하기로 했다. 탐색기법을 사용할 때 완전탐색보다는 이진탐색을 사용하자는 생각으로 자료구조에서 배웠던 것을 떠올려 문제를 풀어보았다. 

 

알고리즘

1. N을 입력받는다.

2. StringTokenizer를 사용하여 arr배열에 N개 만큼 입력시켜준다.

3. high 변수에 max 함수를 사용하여 arr배열과 비교하여 더 높은 high를 담아준다.

4. M을 입력받는다.

5. 이분탐색 기법을 사용하여 mid와 mid-1, mid+1로 나누어준다.

6. arr[i] > mid 이면 arr[i]를 그대로 사용하므로 sum 변수에 mid를 계속 더해준다.

7. 아니라면 sum 변수에 arr[i]변수를 그대로 사용하므로 계속 더한다.

8. 만약 sum이 M 보다 작거나 같으면 low가 mid+1, 아니면 high에 mid-1을 담는다.

9. high 변수를 max와 비교하였으므로 high를 print 한다. high가 상한액이 된다.

 

package selftest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_2512 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int low = 0;
		int high = -1;
		int N = Integer.parseInt(br.readLine());
		
		int arr[] = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		
		for(int i = 0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			high = Math.max(high, arr[i]);
		}
		int M = Integer.parseInt(br.readLine());
		
		//Arrays.sort(arr);
		
		while(low <= high){
			long sum = 0;
			int mid = (low + high) / 2;
			
			for(int i = 0; i<N; i++) {
				if(arr[i] > mid) {
					sum += mid;
				}
				else {
					sum += arr[i];
				}
			}
			if(sum <= M) {
				low = mid + 1;
			}
			else {
				high = mid - 1;
			}
		}
		System.out.println(high);
	}
}

 

 

이렇게 문제를 해결할 수 있었다. 실버3 덕분에 죽을 뻔 했는데, long sum = 0 변수를 while문 밖에서 선언해 주어서 계속해서 75라는 뜬금없는 숫자가 나왔다. 처음이 계속 초기화 되지 않아서 이상한 숫자가 나온 것 같다.