글 읽기 - 자바) 두가지 방법의 이분탐색 차이점

qlsdud0604 2년 전 0

첨부한 소스코드는 오답이라고 나오고 47~52번 라인의 조건식을

if (sum < N)
end = middle - 1;
else if (N <= sum)
start = middle + 1;

이렇게 수정하니까 정답처리가 되네요. 무슨 차이점이 있나요?

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

public class Main {
	static int K;
	static int N;

	static long[] lans;

	static long max = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());

		K = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());

		lans = new long[K];

		for (int i = 0; i < K; i++) {
			lans[i] = Long.parseLong(br.readLine());
			max = Math.max(max, lans[i]);
		}

		bw.write(binarySearch() + "\n");
		bw.close();
	}

	static long binarySearch() {
		long start = 1;
		long end = max;

		while (start <= end) {
			long middle = (start + end) / 2;
			long sum = 0;

			for (long lan : lans) {
				if (middle < lan) {
					sum += (lan / middle);
				}
			}

			if (sum < N)
				end = middle - 1;
			else if (N < sum)
				start = middle + 1;
			else if (sum == N)
				return middle;
		}
		return end;
	}
}

pmn0001 2년 전 0

어떤 길이로 잘랐을 때 N개의 랜선을 만드는 경우는 단 한가지가 아닐 수 있습니다.

else if(N<=sum) start = middle+1; 을 해서 최대한 길게 잘랐을 때까지 N개 이상의 랜선을 만드는 것이고

else if (sum==N) return middle은 잘랐을 때 N개가 되면 바로 return 해버리는 것이라, N개 이상으로 자를 수 있는 최대 길이라고 보장할 수 없습니다.

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

문제

문제

출처

ICPC

자바) 두가지 방법의 이분탐색 차이점

qlsdud0604 2년 전 0

pmn0001 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말