글 읽기 - 32%에서 틀리는데 제 코드 어디가 문제일까요

boysoeng 1년 전 1

이분탐색 많이 어렵네요

제가 짠 로직에서 어느 부분이 잘못되었는지 알려주시면 감사하겠습니다 ㅠㅠㅠ

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N;
    static long M;
    static long[] times;

    public static void main(String[] args) throws IOException {
        String[] split = br.readLine().split(" ");
        N = Integer.parseInt(split[0]);
        M = Long.parseLong(split[1]);
        times = new long[N];
        for (int i = 0; i < N; i++) {
            times[i] = Long.parseLong(br.readLine());
        }
        Arrays.sort(times);
        long left = 1;
        long right = M * times[N - 1];
        long answer = Long.MAX_VALUE;
        
        while (left <= right) {
            long mid = (left + right) / 2;
            long value = calculatePass(mid);
            if (value < M) { // 부족해 -> 더 시간 써야지
                left = mid + 1;
            } else {
                right = mid - 1;
                answer = Math.min(answer, mid);
            }
        }
        System.out.println(answer);
    }

    private static long calculatePass(long time) {
        long answer = 0;
        for (int i = 0; i < N; i++) {
            answer += time / times[i];
        }
        return answer;
    }
}

boysoeng 1년 전 7

calculatePass에서 answer를 찾는 과정에서 answer가 M 초과일 경우 break를 해줘야하더라구요, 안그러면 오버플로우가 발생하는 듯 합니다

dmdrk1414 1년 전 0

100,000 10**9

10**9

일때 중간에 계산을 하는 answer 부분에도 오버플로우가 발생할 수 있다는 걸 이제 알았네요... 감사합니다.

moon1309 1년 전 0

저도 이 부분에서 틀렸는데 이거 혹시 왜 오버플로우인가요..?

answer가 long이니까, n개의 창구(최대 10만개) * m(최대 10억 명)해도 100,000,000,000,000인데 long으로 충분히 가능한 거 아닌가요??ㅠㅠ

jhkim31 1년 전 0

창구수(N) : 1e5

창구당 소요시간 [1, 1, 1, ... , 1e9]

라면

right 최대값 : 1e9 * 1e9 =1e18

mid = 1e18 / 2 = 5e17 로

5e17 / 1 이 N번 더해져서 오버플로 날 수 있네요.

ldw28517 1년 전 2

만약 10억 시간이 소요되는 창구 하나와 1의 시간이 소요되는 창구가 최대(9.999만개)로 존재할 경우를 생각해보면 됩니다.
이 경우 10억명의 사람이 존재한다면, 이분탐색은 다음과 같이 진행할 수 있죠

- 최대 소요시간(right) = 10 * 10억

첫 번째 루프에서 mid는 10억 * 5억이라는 값이 나오게 되고,
sum에 수용 가능한 각 창구의 인원을 누적합 하는 과정에서 1의 시간이 소요되는 창구 때문에
sum += 10억 * 5억 / 1 이라는 연산이 9.999만번 발생하게 되죠.

이경우 sum의 값이 대략 2^75로, long 타입의 범위인 2^64를 넘어 오버플로우가 발생하게 됩니다.

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

문제

문제

출처

ICPC

32%에서 틀리는데 제 코드 어디가 문제일까요

boysoeng 1년 전 1

boysoeng 1년 전 7

dmdrk1414 1년 전 0

moon1309 1년 전 0

jhkim31 1년 전 0

ldw28517 1년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말