글 읽기 - 답은 맞는데 왜 1이 모자른지 모르겠습니다..

tjgy9023 5년 전 0

-1 을 넣으니까 맞긴하는데

왜 1이 모자라는지 모르겠네요..

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

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());
		int[] bgt = new int[n];
		int end = -1;
		int start = 0;
		
		for (int i = 0; i < n; i++) {
			bgt[i] = Integer.parseInt(st.nextToken());
			end = Math.max(end,bgt[i]);
		}
		
		int lim = Integer.parseInt(br.readLine());
		
		while(start<=end) {
			
			int total = 0;
			int mid = (start+end)/2;
			
			for(int i = 0; i < n; i++) {
				total += Math.min(bgt[i], mid);
			}
			
			if(total <= lim)  {
				start = mid + 1;
			}else {
			    end = mid - 1;
			}
		}
		System.out.println(start-1);
	}
}

fin 3년 전 0

저도 이분탐색에 대한 지식이 많지는 않아서 자세히는 모르지만 예상되는 문제점을 말씀드리자면

23~37line에서 구현한 이분탐색이 upper bound이기 때문에 찾을수 있는 가장 큰 값보다 하나 큰 값을 찾는 걸로 보입니다.

다음과 같이 코드를 수정해봤습니다.

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

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());
		int[] bgt = new int[n];
		int end = -1;
		int start = 0;
		
		for (int i = 0; i < n; i++) {
			bgt[i] = Integer.parseInt(st.nextToken());
			end = Math.max(end,bgt[i]);
		}
		
		int lim = Integer.parseInt(br.readLine());
		
		while(start+1<end) {
			
			int total = 0;
			int mid = (start+end)/2;
			
			for(int i = 0; i < n; i++) {
				total += Math.min(bgt[i], mid);
			}
			
			if(total <= lim)  {
				start = mid;
			}else {
			    end = mid;
			}
		}
		System.out.println(start);
	}
}

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

문제

문제

출처

ICPC

답은 맞는데 왜 1이 모자른지 모르겠습니다..

tjgy9023 5년 전 0

fin 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말