글 읽기 - 2512번 문제 설명해주실 수 있는 분

lks0510 3년 전 1

2512번 예산 문제입니다.

각 지방의 예산 요청 n개를 다합쳐 총 예산을 넘지 않는 선에서 개별 예산의 최댓값을 구하는 문제인데요.

예를 들어, 4개의 예산 요청이 각각 120 110 140 150 이고 총 예산이 485일 때

총합이 총 예산을 넘지 않도록 개별 예산의 상한액을 정해서 해당 금액을 넘는 예산은 상한액으로 할당합니다.

120 110 127 127 이렇게 말이죠.

이때 127이 출력되면 됩니다.

이분탐색 문제인 줄 모르고 다음과 같이 알고리즘을 짜봤는데 위의 예에서는 통과했습니다.

그런데 틀렸다고 나오더라고요.

혹시

1. 반례를 제시해주시거나

2. 왜 이분탐색을 써야하는지(검색해보니 이분 탐색 문제라고 하더군요.)

설명해주실 수 있는 분 있으시면 댓글 부탁드립니다.

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

public class Main{   
    public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System. in));
      BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      int n = Integer.parseInt(br.readLine());
      int[] req = new int[n];
      int sum=0;

      StringTokenizer st = new StringTokenizer(br.readLine());
      for(int i=0;i<n;i++){
        req[i] = Integer.parseInt(st.nextToken());
        //각 지방의 예산 요청을 배열에 저장
        sum+=req[i];
      }

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

      if(sum<=m){

        int max=req[0];
        for(int i=1;i<n;i++){
          if(req[i]>max){max=req[i];}
        }
        System.out.print(max);

      } else{

        double mean = (double)m/n;
        int count=0;

        for(int i=0;i<n;i++){
          if(req[i]<mean){
            m-=req[i];
            count++;
          }
        }

        m/=(n-count);
        System.out.print(m);
      }

    }
}

qwer9412 3년 전 1

반례

4
1 5 6 100
18

결과 : 5

정답 : 6

lks0510 3년 전 0

덕분에 이해됐습니다! 감사합니다.

anginjunddi 3년 전 0

왜 6이 나와야 하죠? 4가 나와야 전부 줄 수 있지 않나요?

fbfbf1 3년 전 0

@anginjunddi

4면

1 4 4 4 이므로 13이므로 예산안에서 줄 수 있기는 하나

문제에서 요구하는건 최대값이므로

6일 때는

1 5 6 6 이면 딱 18 만족 할 수 있으므로

6입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2512번 문제 설명해주실 수 있는 분

lks0510 3년 전 1

qwer9412 3년 전 1

lks0510 3년 전 0

anginjunddi 3년 전 0

fbfbf1 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말