글 읽기 - 이분 탐색 상한 설정에 대한 질문입니다 ㅠㅠ 알려주세요 부탁드립니다.

dntjd1081 4년 전 0

low와 hi를 설정하는데 있어 hi가 기존의 휴게소들 사이의 길이보다 커질 수 없다고 생각해서

각 인접한 휴게소들 사이의 거리 중 가장 큰 값으로 설정했습니다.

하지만 이런방식으로 하면 틀리고 주석친 부분처럼

hi=L; 로해야 정답으로 나오네요 ㅠㅠ

혹시 제가 처음에 했던 방식처럼하는 경우 어떤부분에서 문제가 생기는지 알려주실 수 있으신가요? 부탁드립니다

import java.util.Scanner;
import java.util.Arrays;

public class Main {
	static int N,M,L;
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		M=sc.nextInt();
		L=sc.nextInt();
		int[]R=new int[N+2];
		int lo=1,hi=0;
		for(int i=1;i<=N;++i)
			R[i]=sc.nextInt();
		R[0]=0;
		R[N+1]=L;
		Arrays.sort(R);
		
		for(int i=1;i<N+1;++i)
			hi=Math.max(hi, R[i]-R[i-1]+1);
		
        //hi=L;
		while(lo<=hi) {
			//휴게소가 mid 이상일 수 있나?
			int mid=(lo+hi)/2;
			int built=0;
			
			for(int i=1;i<R.length;++i) {
				if(R[i]>R[i-1])
					built+=(R[i]-R[i-1]-1)/mid;
			}
			
			if(built>M)
				lo=mid+1;
			else
				hi=mid-1;
		}
		System.out.println(lo);
	}
}

sait2000 4년 전 0

지금 있는 마지막 휴게소에서 도로 끝 까지의 거리가 고려에서 빠진 것 같은데요

dntjd1081 4년 전 0

아 그부분을 생각을 못했네요 ㅠㅠㅠㅠ 정말 정말 감사합니다!!!

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

문제

문제

출처

ICPC

이분 탐색 상한 설정에 대한 질문입니다 ㅠㅠ 알려주세요 부탁드립니다.

dntjd1081 4년 전 0

sait2000 4년 전 0

dntjd1081 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말