글 읽기 - [java] 제 로직의 오류를 알 수 있을까요?

ayoung52 2년 전 0

제가 푼 로직은

집들을 입력받아 정렬시킨다.
공유기 설치 최대거리를 구하기 위해 이분 탐색을 진행한다.
해당 거리(mid) 이상인 집이 C개 이상 있는지 확인한다.
C개 이상 있을 경우, result 값을 갱신한다.

입니다.

제가 생각하기에는 isPossible 메소드(3번 로직을 잘못 짠 거 같은 느낌입니다.)에서 틀린 것 같은데,

아무리 생각해도 어떤 로직이 틀렸는 지 모르겠습니다 ㅠㅠ

도움 주실 수 있을까요?

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


public class Main {

	static int N, C;
	static long result;
	static int[] house;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer sk = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(sk.nextToken());
		C = Integer.parseInt(sk.nextToken());
		house = new int[N];
		
		for (int i = 0; i < N; i++) {
			house[i] = Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(house);
		
		BinarySearch();
		
		System.out.println(result);
	}

	private static void BinarySearch() {
		long min = house[0];
		long max = house[N - 1];
		long mid = 0;
		
		while (min <= max) {
			mid = (min + max) / 2;
			
			if (isPossible(mid)) {
				result = Math.max(result, mid);
				min = mid + 1;
			} else {
				max = mid - 1;
			}
		}
	}

	private static boolean isPossible(long mid) {
		boolean isposs = false;
		int cnt = 1;
		int n = 0;
		
		for (int i = 0; i < N - 1; i++) {
			if (house[n] + mid <= house[i + 1]) {
				cnt++;
				n = i + 1;
			}
		}
		
		if (cnt >= C) isposs = true;
		
		return isposs;
	}

}

djm03178 2년 전 2

이분 탐색의 범위는 거리 후보의 최소와 최대이므로, min의 시작이 house[0]여서는 안 됩니다. house는 단순히 좌표를 나타낼 뿐이므로, 정답은 이보다 작은 값이 될 수 있습니다. min만 1로 초기화해주면 맞습니다.

ayoung52 2년 전 0

감사합니다...ㅠㅠㅠ...

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

문제

문제

출처

ICPC

[java] 제 로직의 오류를 알 수 있을까요?

ayoung52 2년 전 0

djm03178 2년 전 2

ayoung52 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말