글 읽기 - 반례를 못찾겠습니다..ㅠㅠ

kwonmminji 5년 전 0

이분탐색으로 아래와 같이 구현했습니다.

예제도 맞고, 데이터를 만들어 돌려보는데 자꾸 틀렸다고 나오네요.

어떤 경우에 답이 안맞는 건지 못찾겠습니다.

어디가 문제일까요?

도와주시면 정말 감사하겠습니다!

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String input = br.readLine();
		StringTokenizer st = new StringTokenizer(input);
		int n = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		
		int[] posArr = new int[n];
		for (int i = 0; i < n; i++) {
			posArr[i] = Integer.parseInt(br.readLine());
		}
	
		Arrays.sort(posArr);
		
		bw.write(getDistance(posArr, c) + "\n");
		bw.flush();
		bw.close();
	}
	
	public static int getDistance(int[] pos, int count) {
		int left = 0;
		int right = pos[pos.length - 1] - pos[0];
		int mid = 0;
		int result = mid;
		
		while (left <= right) {
			mid = (left + right) / 2;
			
			int cnt = 1;
			int start = pos[0];
			for (int i = 1; i < pos.length; i++) {
				// 공유기 설치
				if (pos[i] - start >= mid) {
					cnt++;
					start = pos[i];
				}
			}
			
			if (cnt >= count) left = mid + 1;
			else right = mid - 1;
			
			if (cnt == count) result = mid;
		}
		
		return result;
	}
}

djm03178 5년 전 5

49번째 줄의 조건에 한 번도 걸리지 않을 수 있습니다.

4 3

kwonmminji 5년 전 0

해결했습니다!! 감사합니다 ㅠㅠ

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

문제

문제

출처

ICPC

반례를 못찾겠습니다..ㅠㅠ

kwonmminji 5년 전 0

djm03178 5년 전 5

kwonmminji 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말