★★★ [백준][Java] 1654번 랜선 자르기 (이진탐색) #2

#2

point (이것 때문에 승률이 20%에 머무르는 것임)

1. left값은 0이 아닌 1이어야만한다

2. left right res의 자료형을 long으로 선언해주어야한다.

 

 

처음 시작할 때 min이 0, max가 2^31 -1 정도라고 치면

min = (0 + 2^31-1) / 2 + 1

max = 2^31-1 이 되어서 min + max 값이 int범위를 초과할 수 있습니다.

출처 : https://www.acmicpc.net/board/view/6449

 

이게 2^31이 최대값이니까 당연히 int형이 모든 수를 담을 수 있을 것이라고 생각했는데

mid = (left+right)/2하는 과정에서의 (left+right)부분에서 int형의 최대값을 초과하기 때문에

long으로 해주어야 한다는 것이다.. 만일 적당히 랜선의 최대값이 2^29 혹은 2^30정도였으면 .. 상관없었을듯?

 

 

 

 

 

가장 중요한 부분이 left값임..

이게 랜선이라는 객체가 0이라는 값이

존재하지 않기 때문에 최소값을 1로 설정해주어야함

 

UpperBound는 제대로 한 것이 맞는데

자료형을 long대신 int를 했고

랜선의 최소값의 후보를 1이 아닌 0으로 했기 때문에

틀렸습니다를 약 5번정도 볼 수 있었던 것.

 

 

(↓ 이건.. 그냥 코드 짜는 방식의 차이인듯

문제에서 요구하는 이분탐색의 조건

left<right이든 left<=right이든 둘다 만족 가능함)

 

솔직히 봐도 모르겠음 

UpperBound를 하려면 right에 +1을 해줘야하고

left<=right를 안 쓰고 left<right를 쓰고

right = mid-1 도 right = mid

뭐 이렇게 하는 것 같은데 

한 5번은 봐야 이해할 수 있을드,ㅅ...

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static void main(String[] args) throws IOException{
        String[] arr = br.readLine().split(" ");
        int K = stoi(arr[0]);
        int N = stoi(arr[1]);
        long left = 0;
        long right = 0;
        
        int[] lanArr = new int[K];
        for(int i=0; i<K; i++) {
            lanArr[i] = stoi(br.readLine());
            right = Math.max(right, lanArr[i]);
        }
        right++;    
        
        
        long res = 0;
        while(left<right) {
            long mid = (left+right)/2;
            
            long num = 0;
            for(int lan : lanArr)
                num += (long)(lan/mid);
 
            if(num<N)
                right = mid;
            else { 
                left = mid+1;
                res = mid;
            }
            
        }
        
        System.out.println(res);
        
        
        
        
//        bw.write("");
//        bw.flush();
//        bw.close();
    }
 
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
}