글 읽기 - 이분탐색에 대한 질문입니다

le_effort 3년 전 0

코드를 첨부하였고 맞은 코드입니다.

다만 궁금한 점이 있어서 질문을 올립니다.

이분탐색만으론 정확한 값을 얻어내지 못하는 건가요?

27-29번째 줄을 없애면 틀렸다고 나와서 이분탐색만으론 정확한 값을 못 구하는것인지 궁금합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
	
	static int n,m;
	static int ans = 0;
	static ArrayList<Integer>list =  new ArrayList<>();
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		int sum = 0;
		int max = 0;
		String [] t = br.readLine().split(" ");
		
		for(int i=0; i<n; i++) {
			int num = Integer.parseInt(t[i]);
			list.add(num);
			sum+=num;
			max = Math.max(max, num);
		}
		
		m = Integer.parseInt(br.readLine());		// 총 예산
		
		if(sum <=m) {
			System.out.println(max);
		}
		else {
			Collections.sort(list);
			int start = 1;
			int end = m;
			
			while(start<= end) {
				int mid = (start+end)/2;
				long tmp = 0;
				
				for(int i=0; i<n; i++) {
					if(list.get(i) > mid) {
						tmp+=mid;
					}
					else {
						tmp+=list.get(i);
					}
				}
	
				if(tmp > m) {
					end = mid-1;
				}
				else {
					ans = Math.max(ans, mid);
					start = mid+1;
				}
			}
			System.out.println(ans);
		}

	}
}

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

문제

문제

출처

ICPC

이분탐색에 대한 질문입니다

le_effort 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말