글 읽기 - 틀렸다고 나오는데 반례 좀 찾아주실 수 있으신가요 ..?

cncn6666 3년 전 0

제가 찾은 반례로 테스트 할 때는 다 맞게 답이 나오는 것 같은데

돌려보면 틀렸다고 나오네요 ㅠㅠ

혹시 반례 좀 찾아주실 수 있으신가요 ?

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt(); // 지방의 수

        int tMax = 0;

        // 각 지방의 예산요청
        int[] city = new int[N];
        for (int i = 0; i < N; i++) {
            int value = city[i] = scan.nextInt();
            tMax = Math.max(value, tMax);
        }

        int M = scan.nextInt(); // 총 예산
        int min = M / N; // 최소값
        int max = tMax; // 최대값

        // 배정할 수 있는 예산 중, 최대값 계산 시작하기
        while (min + 1 < max) {
            long sum = 0;
            // 중간값 구하기
            int mid = (min + max) / 2;
            for (int i = 0; i < N; i++) {
                // 1. 해당 요청이 중간값(정수 상한액)을 넘을 경우, 중간값으로 배정하기
                if (city[i] > mid) {
                    sum += mid;
                    // 2. 해당 요청이 중간값을 넘지 않을 경우, 그대로 배정하기
                } else {
                    sum += city[i];
                }
            }

            // 요청들의 총합이 전체국가예산과 같을 경우 리턴하기
            if (sum == M) {
                min += 1;
            } else if (sum > M) {
                max = mid;
                // 요청들의 총합이 전체국가예산을 넘지 않을 경우
            } else {
                min = mid;
            }
        }

        // min은 부여할 수 있는 값 중 최대값
        // max는 부여할 수 없는 값 중 최소값이다.
        System.out.println(min);
    }

}

wbjeon2k 3년 전 2

이 코드로 아래 예시를 돌리면 정답이 500으로 나오는데,

제것 포함 여러 정답소스들 기준으로

정답은 497

나왔습니다.

100
384 387 278 416 294 336 387 493 150 422 363 28 191 60 264 427 41 427 173 237 212 369 68 430 283 31 363 124 68 136 430 303 23 59 70 168 394 457 12 43 230 374 422 420 285 38 199 325 316 371 414 27 92 481 457 374 363 171 497 282 306 426 85 328 337 6 347 230 314 358 125 396 83 46 315 368 435 365 44 251 88 309 277 179 289 85 404 152 255 400 433 61 177 369 240 13 227 87 95 40 
50000

cncn6666 3년 전 0

감사합니다! 다시 생각해봐야겠네요!

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

문제

문제

출처

ICPC

틀렸다고 나오는데 반례 좀 찾아주실 수 있으신가요 ..?

cncn6666 3년 전 0

wbjeon2k 3년 전 2

cncn6666 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말