백준 - 랜선자르기 (JAVA)

 

 

백준 랜선자르기 문제이다.

 

이분탐색의 기초 문제라고 생각한다.

 

일단 생각해야 하는 조건들은 다음과 같다.

 

1. min 값과 max 값

- 최소로 자를 값은 1이된다. 0이 될 수 없는이유는 어차피 0으로 잘라도 의미가 없기 때문이다.

- max값은 각 줄마다 줄의 길이를 받아오면서 Math.max매서드를 통해 max값을 업데이트 시켜준다.

- max/min값을 구하기 위해서는 기존 mid값보다 +1 을 해주거나 -1을 해주어야 한다. 만약 min, max 값이 각각 400, 401일경우 

mid = (max+min) /2 를 하게 되는데 이는 다시 400이다. 즉 무한루프 가능성이 있다. 따라서 +1, -1을 꼭 해주어야한다.

 

2. 다시 mid값을 설정하러 반복을 돌아야 하는 조건

- 정답을 예시로 200으로 자르던 199로 자르던 198로 자르던 결국 11개가 나오는 것은 똑같다. 하지만 가장 큰 값을 구해야 함으로 while의 조건 내부를 같을때로 설정하고 자르는 갯수가 동일한 경우에도 최대값을 찾을 수 있게 설정했다.

 

 

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

public class 백준_랜선자르기 { //5시 시작
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int K = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken()); //만들어야 하는 랜선의 갯수

        int[]list = new int[K];

        long max = 0;
        long min = 1;
        long answer = 0;

        for(int i = 0; i < K; i++){
            list[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, list[i]);
        }
        //자를 수 있는 길이중에 가장 큰 길이를 구해야한다. 그렇기 위해서는 이분탐색을 통해 길이를 구해야한다.
        //이분탐색 로직안에서 여러개의 리스트를 자르는 로직이들어가야함.
        while(min <= max){ //같은 값으로 하는 이유는 두개가 같아졌을때도 잘라야하기 때문이다.
            long mid = (min+max) / 2; //중간 값.
            long count = 0;
            for(int i =0 ;i<K; i++){
                count += list[i] / mid; //전체 몇개로 잘렸는지 나옴
            }
            if(count < N){ // 잘라야하는 랜선의 갯수보다 적은 갯수로 잘렸으면 너무 크게 잘랐다는 뜻임으로 max기준점을 냊춰주어야한다.
                max = mid -1;
            }else{ //잘라야 하는 랜선의 갯수보다 같거나 더 많이 자른경우는 mid를 min+1값으로 옮겨서 한번 더 테스트해본다
                answer = mid; //여기서 먼저 선언이 되어야한다.
                min = mid+1;

            }
        }
        System.out.println(answer);

    }
}