[백준] 2512 예산 - Java

 

 

문제 출저

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

2512번: 예산

 

 

 

문제 풀이

주어진 예산을 최대로 쓰는 상한액을 구하는게 이 문제의 요구사항입니다.

 

상한액을 구하기 위해 이분 탐색을 활용했습니다.

int[] board에 주어진 값을 담았습니다.

이분 탐색을 위해 상한액의 범위를 int s, int e로 선언했습니다.

 

int s 는 가장 작은 값으로 0을 했습니다. 

상한액의 최대 한도(e)는 주어진 예산 값 중 가장 큰 값으로 했습니다

 

while(s <= e) 를 탐색하면서 

int result를 선언하였고

int mid = (s+e)/2 탐색 상한액인 mid 보다 큰 값은 mid로 작은 값은 board[i]를 result에 더해 예상 예산안을 만들었습니다.

result가 총 예산보다 크다면  s = mid + 1, 작다면 e = mid - 1로 해서 탐색을 해 정답을 구했습니다.

 

 

 

소스 코드

package baekjoon.backjoon9.day16;

/*
예산
https://www.acmicpc.net/problem/2512
 */

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

public class B2512 {

    static int n;
    static int[] board;
    static int m;


    static int answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        board = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        int sum = 0;
        int big = 0;
        for(int i = 0; i < n; i++) {
            board[i] = Integer.parseInt(st.nextToken());
            sum += board[i];
            big = Math.max(big, board[i]);
        }
        m = Integer.parseInt(br.readLine());



        int s = 0;
        int e = big;

        while(s <= e) {
            int mid = (s+e)/2;

            int result = 0;
            for(int i = 0; i < n; i++) {
                if(board[i] > mid) {
                    result += mid;
                }
                else {
                    result += board[i];
                }
            }

            if(result <= m) {
                s = mid + 1;
                answer = mid;
            }
            else {
                e = mid - 1;
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(answer);
        System.out.println(sb);

    }

}