글 읽기 - 반례 부탁드리겠습니다.

kodong 2년 전 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 IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st;
		
		String nm = br.readLine();
		
		st = new StringTokenizer(nm, " ");
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		int[] arr = new int[n];
		
		String ms = br.readLine();
		st = new StringTokenizer(ms, " ");
		
		int max = 0;
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			
			if(arr[i] > max)
				max = arr[i];
		}
		
		System.out.print(binary(arr, m, max));
	}
	
	public static int binary(int[] arr, int m, int max) {
		int left = 0;
		int right = max;
		
		while(left <= right) {
			long sum = 0;
			int mid = (left+right)/2;
			
			for(int i=0; i<arr.length; i++) {
				if(arr[i] >= mid) {
					sum += arr[i] - mid;	
				}
			}
			if(sum == m)
				return mid;
			else if(sum > m) { 
				left = mid+1;
			}
			else {
				right = mid-1;
			}
		}
		return 0;
	}
}

pmn0001 2년 전 1

반례입니다

3 5
2 3 7

kodong 2년 전 0

나무를 하나만 자를 때를 생각을 안 했네요 감사합니다.

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

문제

문제

출처

ICPC

반례 부탁드리겠습니다.

kodong 2년 전 1

pmn0001 2년 전 1

kodong 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말