[백준] 예산

문제 주소

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

2512번: 예산

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

www.acmicpc.net

문제 설명

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

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

예를 들어, 전체 국가예산이 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

예제 입력 2

5
70 80 30 40 100
450

예제 출력 2

제출 코드

import java.io.*;
import java.util.*;
import java.lang.Math;

public class Main {

    static int [] countries;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());//국가의 개수

        countries = new int[n];

        int biggest = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){
            int x = Integer.parseInt(st.nextToken());
            countries[i] = x;
            if(biggest<x){
                biggest = x;
            }
        }

        int m = Integer.parseInt(br.readLine());//총예산

        Arrays.sort(countries);

        int min = 0;
        int max = m;
        int limit = 0;//예산 한도, 상한액

        while(min<=max){
            int mid = (min+max)/2;//-> 상한액
            int sum = 0;

            for(int i=0;i<n;i++){//countries를 돌면서 예산으로 가능한지 봐봄

                if(countries[i]>=mid){//상한액보다 같거나 크면
                    sum += mid;
                }else{//상한액보다 작으면
                    sum += countries[i];
                }
            }

            if(sum>m){//저 상한액으로 필요한 예산이 총 예산보다 크면
                max = mid-1;//상한액을 내린다
            }else if(sum==m){//필요한 예산이 총 예산과 같으면
                limit = Math.max(limit,mid);
                max = mid-1;
            }else{//필요한 예산이 총 예산보다 작으면
                limit = Math.max(limit,mid);
                limit = Math.min(biggest,limit);
                min = mid+1;//상한액을 올린다
            }
        }
        System.out.println(limit);

    }
}

코드 설명

구해야 하는 것 예산의 상한액 -> 구해야 하는 것이 mid이다

국가 배열을 돌면서 예산을 계산함

상한액에 따라 필요한 예산과 총 예산을 비교해서 상한액을 올리거나 줄이는데

문제 조건에서 필요한 예산이 총 예산보다 작으면 limit이 biggest(나온 예산 원소중에 제일 큰 것) 이상으로 올라갈 수 없도록 하라고 해서 Math.min으로 비교해줌

풀이 과정

이렇게 짜봤는데요

import java.io.*;
import java.util.*;
import java.lang.Math;

public class Main {

    static int [] countries;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());//국가의 개수

        countries = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){
            countries[i] = Integer.parseInt(st.nextToken());
        }

        int m = Integer.parseInt(br.readLine());//총예산

        Arrays.sort(countries);

        int min = 0;
        int max = m;//-> 아 뭐지.. 최댓값 뭐지 진짜.. 예산으로 넣어봄 일단
        int limit = 0;//예산 한도, 상한액

        while(min<=max){
            int mid = (min+max)/2;//-> 이걸 상한액으로 써봄
            int sum = 0;

            for(int i=0;i<n;i++){//countries를 돌면서 예산으로 가능한지 봐봄...?

                if(countries[i]>=mid){//상한액보다 같거나 크면
                    sum += mid;
                }else{//상한액보다 작으면
                    sum += countries[i];
                }
            }

            if(sum>m){//저 상한액으로 필요한 예산이 총 예산보다 크면
                max = mid-1;//상한액을 내린다
            }else{//필요한 예산이 총 예산과 같거나 작으면
                limit = Math.max(limit,mid);
                min = mid+1;//상한액을 올린다
            }
        }
        System.out.println(limit);

    }
}

단단히 망하고 말았습니다

4
120 110 140 150
485
0
127

5
70 80 30 40 100
450
450

if(sum>m){//저 상한액으로 필요한 예산이 총 예산보다 크면
                max = mid-1;//상한액을 내린다
            }else{//필요한 예산이 총 예산과 같거나 작으면
                limit = Math.max(limit,mid);
                min = mid+1;//상한액을 올린다
            }

→

if(sum>m){//저 상한액으로 필요한 예산이 총 예산보다 크면
                max = mid-1;//상한액을 내린다
            }else if(sum==m){
                limit = Math.max(limit,mid);
                break;
            }else{//필요한 예산이 총 예산보다 작으면
                limit = Math.max(limit,mid);
                min = mid+1;//상한액을 올린다
            }

5 70 80 30 40 100 450 450

뭘까 대체…

로그 찍어봄~~

100이 나와야 하는데 왜 큰 쪽으로만 가죠..?

100이 가장 커서 그거여야 하는데 어디로 가는거임,,,

5
70 80 30 40 100
450
0-450 mid:225 sum:320 m:450
226-450 mid:338 sum:320 m:450
339-450 mid:394 sum:320 m:450
395-450 mid:422 sum:320 m:450
423-450 mid:436 sum:320 m:450
437-450 mid:443 sum:320 m:450
444-450 mid:447 sum:320 m:450
448-450 mid:449 sum:320 m:450
450-450 mid:450 sum:320 m:450
450

필요한 예산이 총 예산보다 작으면 limit이 biggest(나온 예산 원소중에 제일 큰 것) 이상으로 올라갈 수 없도록 함…

if(sum>m){//저 상한액으로 필요한 예산이 총 예산보다 크면
                max = mid-1;//상한액을 내린다
            }else if(sum==m){//필요한 예산이 총 예산과 같으면
                limit = Math.max(limit,mid);
                max = mid-1;
            }else{//필요한 예산이 총 예산보다 작으면
                limit = Math.max(limit,mid);
                limit = Math.min(biggest,limit);
                min = mid+1;//상한액을 올린다
            }

똑바로 나왔다…

5
70 80 30 40 100
450
0-450 mid:225 sum:320 m:450
226-450 mid:338 sum:320 m:450
339-450 mid:394 sum:320 m:450
395-450 mid:422 sum:320 m:450
423-450 mid:436 sum:320 m:450
437-450 mid:443 sum:320 m:450
444-450 mid:447 sum:320 m:450
448-450 mid:449 sum:320 m:450
450-450 mid:450 sum:320 m:450
100

import java.io.*;
import java.util.*;
import java.lang.Math;

public class Main {

    static int [] countries;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());//국가의 개수

        countries = new int[n];

        int biggest = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){
            int x = Integer.parseInt(st.nextToken());
            countries[i] = x;
            if(biggest<x){
                biggest = x;
            }
        }

        int m = Integer.parseInt(br.readLine());//총예산

        Arrays.sort(countries);

        int min = 0;
        int max = m;//-> 아 뭐지.. 최댓값 뭐지 진짜.. 예산으로 넣어봄 일단
        int limit = 0;//예산 한도, 상한액

        while(min<=max){
            int mid = (min+max)/2;//-> 이걸 상한액으로 써봄
            int sum = 0;

            for(int i=0;i<n;i++){//countries를 돌면서 예산으로 가능한지 봐봄...?

                if(countries[i]>=mid){//상한액보다 같거나 크면
                    sum += mid;
                }else{//상한액보다 작으면
                    sum += countries[i];
                }
            }

            System.out.println(min+"-"+max+" mid:"+mid+" sum:"+sum+ " m:"+m);

            if(sum>m){//저 상한액으로 필요한 예산이 총 예산보다 크면
                max = mid-1;//상한액을 내린다
            }else if(sum==m){//필요한 예산이 총 예산과 같으면
                limit = Math.max(limit,mid);
                max = mid-1;
            }else{//필요한 예산이 총 예산보다 작으면
                limit = Math.max(limit,mid);
                limit = Math.min(biggest,limit);
                min = mid+1;//상한액을 올린다
            }
        }
        System.out.println(limit);

    }
}

맞았습니다!!

저작자표시

'Coding Test' 카테고리의 다른 글

[프로그래머스] 이모티콘 할인행사 (0)	2024.04.17
[백준] 나무 자르기 (0)	2024.04.16
[백준] 세탁소 사장 동혁 (0)	2024.04.16
[백준] A → B (0)	2024.04.16
[백준] 카드 정렬하기 (0)	2024.04.11

Greedeveloper

[백준] 예산

문제 주소

문제 설명

입력

출력

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

제출 코드

코드 설명

풀이 과정

'Coding Test' 카테고리의 다른 글

티스토리툴바

[백준] 예산

문제 주소

문제 설명

입력

출력

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

제출 코드

코드 설명

풀이 과정

'Coding Test' 카테고리의 다른 글

관련글

티스토리툴바