백준 2512번 풀이 c++ and java

문제

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다. 

여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.

입력

첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다. 

출력

첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다. 

예제 입력 1 복사

4
120 110 140 150
485

예제 출력 1 복사

127

예제 입력 2 복사

5
70 80 30 40 100
450

예제 출력 2 복사

100

 

 

간단한 이분탐색 문제이다.

 

문제의 로직

 

1. 입력을 모두 받아준다.

2. 이분탐색을 위해 오름차순으로 정렬해 준다.

3. left = 0; right = v[n-1]을 선언해 준다. (이때 중요한 점은 left를 정렬을 했다고 v[0]를 하면 안된다. 0부터 중간값을 찾아서 탐색을 해줘야지 더 자세한 이분탐색 결과값이 나온다. 나는 v[0]을 했다가 오답처리를 받았다.)

4. left + right를 2로 나눈 middle값보다 작은 v[i]값은 그대로 더해주고 더 큰 값들은 middle만큼만 더해준다.

5. 만약 모두 더해준 sum값이 기준값보다 크다면 left = middle +1, 결과값을 저장해둔다.

6. 결과값중에 제일 큰값을 출력한다.

 

 

- c++

 

#include <iostream>
#include <vector>
#include <bits/stdc++.h>

using namespace std;
int n,m;
vector<int>v;

int main() {
    cin >> n;

    for(int i = 0 ; i < n ; i++){
        int a;
        cin >> a;
        v.push_back(a);
    }
    cin >> m;

    sort(v.begin(),v.end());

    int left = 0;
    int right = v[n-1];
    int result,sum;

    while(left<=right){
        sum=0;
        int middle = (left+right)/2;
        for(int i = 0 ; i < v.size(); i++){
            sum += min(middle,v[i]);
        }
        if(m>=sum){
            result = middle;
            left = middle+1;
        }else{
            right = middle-1;
        }
    }

    cout << result <<"\n";





    return 0;
}

 

- java

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

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        ArrayList<Integer> al = new ArrayList<Integer>();

        while(st.hasMoreTokens()){
            al.add(Integer.parseInt(st.nextToken()));

        }

        int m = Integer.parseInt(br.readLine());

        Collections.sort(al);


        int left =0;
        int right = al.get(al.size()-1);
        int middle = 0;
        int result = 0;
        int sum = 0;

        while(left<=right){
            sum = 0;
            middle = (left+right)/2;

            for(int i = 0; i <n; i++){
                sum += Math.min(al.get(i),middle);
            }

            if(sum<=m){
                left = middle+1;
                result = middle;
            }else{
                right = middle-1;
            }
        }

        System.out.println(result);

    }
}