글 읽기 - 자료형에 대해서 질문하고싶습니다.

wkddnjsdlr 3년 전 0

안녕하세요 이분 탐색을 이용한 풀이에서 long 타입을 쓰는 이유는 mid 값을 선정할 때 최악의 경우 10억 + 21억이 되어 integer overflow가 발생한다고 알고 있고, 저 또한 long 타입으로 문제를 해결하였습니다.

하지만 의문인게 int 타입을 이용해서 mid 값을 지정하려 한다면 (start + end) / 2 가 아닌 start + (end - start) / 2 로 지정하면 integer 범위 내라 overflow가 발생하지 않지 않나요?

해당 방법으로 제출을 하면 55%에서 시간 초과가 납니다.

import java.io.*;
import java.util.*;

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[] kn = br.readLine().split(" ");
        int k = Integer.parseInt(kn[0]);
        int n = Integer.parseInt(kn[1]);
        int[] arr = new int[k];
        
        int max = 0;
        
        for(int i = 0; i < k; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, arr[i]);
        }
        
        int start = 1;
        int end = max;
        int answer = 0;
        
        while(start <= end) {
            int count = 0;
            int mid = start + (end - start) / 2; // 나눌 값 
            for(int i = 0; i < arr.length; i++) {
                count += arr[i] / mid;
            }
            
            if(count >= n) {
                answer = Math.max(answer, mid);
                start = mid + 1;
            }else {
                end = mid - 1;
            }
        }
        
        
        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
    }
}

slah007 3년 전 0

count의 오버플로우로 인해 무한루프가 생깁니다.

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

문제

문제

출처

ICPC

자료형에 대해서 질문하고싶습니다.

wkddnjsdlr 3년 전 0

slah007 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말