글 읽기 - 70%대에서 런타임에러가 뜹니다

citizen 6년 전 0

이분탐색으로 최댓값을 구현하는 코드를 짜봤구요..

똑같이 N개로 나눌 수 있으면서 길이를 최대로 하기 위해서

middle을 (start+end+1)/2로 잡아두었습니다. (cnt == N인 경우에도 solve(middle, end)를 하기 위함이죠)

런타임에러로 가능해보이는 요소는

스택오버플로우나, 배열인덱스크기를 벗어나가나 일 것 같은데

위의 두 경우는 여러가지 테스트를 해보면서 에러를 일으키는 요소는 아닌것 같다고 추측했습니다.

코드에서 Int범위를 넘을 수 있는 cnt도 long자료형으로 선언해줬습니다.

문제가 되는 부분을 지적해주셨으면 합니다

import java.util.*;
import java.awt.List;
import java.io.*;
import java.math.*;
 
public class Main{
    public static BufferedReader br = 
            new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = 
            new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static int K, N;
    public static int[] arr;
    
    public static void main(String args[]) throws IOException{
    	Scanner sc = new Scanner(System.in);
    	StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    	K = Integer.parseInt(st.nextToken());
    	N = Integer.parseInt(st.nextToken());
    	int max = 0;
    	arr = new int[K];
    	for(int i = 0; i < K; i++){
    		arr[i] = Integer.parseInt(br.readLine());
    		if(max < arr[i]) max = arr[i];
    	}
    	bw.write(solve(1, max)+"\n");
        bw.close();
    }
    
    public static int solve(int start, int end){
    	if(start == end) return start;
    	int middle = (start+end+1)/2;
    	int place = 0;
    	long cnt = 0;
    	while(place < K){
    		cnt += arr[place]/middle;
    		place++;
    	}
    	if(cnt < N) return solve(start, middle-1);
    	else return solve(middle, end);
    }
}

yohan5050 6년 전 1

예전에 저도 런타임 에러 받아서 질문했었는데 원인이 같아 보이네요 (https://www.acmicpc.net/board/... )

입력값으로 2의 31제곱-1 값이 들어오고,

start = (1+2의 31제곱-1)/2 이 되고, end=2의 31제곱 -1일 경우

start+end에서 int형 범위를 넘어갑니다.

citizen 6년 전 1

그런 문제가 발생하는군요..

대단히 감사합니다

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

문제

문제

출처

ICPC

70%대에서 런타임에러가 뜹니다

citizen 6년 전 0

yohan5050 6년 전 1

citizen 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말