백준 - 이분 탐색 1654번 랜선 자르기 / 풀이,오답

= 처음 접근 방법 (틀림) =

접근을 못했다.

숫자 카드2를 응용해서 풀 수 있는 문제였는데, index로만 생각해봤지 이렇게 길이를 쪼개서 이분 탐색을 한다는 것을 새로 배웠다.

 

구글링을 통해 다른 사람의 풀이를 보고도 이해하는데 조금 오래걸렸다.

 

되게 단순한 문제였는데 더 열심히해야겠다.

 

= 풀이 = 

어떻게 접근해서 해결했는지 알아보자

https://byungil.tistory.com/205

백준 - 이분 탐색 10816 숫자 카드2 문제 / 복습

이 문제랑 거의 똑같다고 생각하면 된다.

 

1. 길이의 최댓값을 이용해서 반으로 쪼갠다. 

여기서 주의할 점은(30번째 줄) max++에 대한 이유인데,

예외를 생각한 것이다. 

내가 랜선을 1개 갖고 있고 필요한 랜선은 1개고 주어진 랜선의 길이가 1일 때를 생각해보자.

 

그럼 당연히 1이라는 출력값이 나올텐데, mid를 구하는 과정에서 (0 + 1) / 2로 mid == 0,

39번째 줄 count를 구할 때, 1 / 0 이라는 예외가 발생하기 때문에 max++을 해줬다.

 

2. 최댓값을 구해야 되기 때문에 upperBound형식을 이용해야 된다.

이 문제는 198로 나누어도, 199로 나누어도 n은 11이라는 값을 얻을 수 있는데

길이의 최대는 200이기 때문에 

if (count < n) {
    max = mid;
} else {
    min = mid + 1;
}

이 식을 사용하는 것이다.

 

while문 조건 자체가 min < max이기 때문에,

198일 때 199일 때도 반복문을 통해서 계속 돌아가고 

마지막 200일 때 min = mid + 1이라는 값으로 인해 while문이 종료 될 수 있다.

 

그리고 마지막 min - 1을 출력하면 내가 원하는 최댓값을 구할 수 있다 !

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class ReMain {
    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()); // 갖고 있는 랜선의 개수 k
        int n = Integer.parseInt(st.nextToken()); // 필요한 랜선의 개수 n
 
        int[] arr = new int[k]; // 랜선의 길이를 담는 배열 arr
 
        /*
         k개의 랜선을 잘라서 n개의 랜선을 만들어야 된다.
         길이의 최댓값을 구하려면 어떻게 해야 될까?
         */
 
        // 1. 랜선 k개 중 제일 긴 길이를 이용해서 이분 탐색 알고리즘을 사용하자.
        long max = 0;
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, arr[i]);
        }
        max++;
 
        long min = 0;
        long count = 0;
 
        while (min < max) {
            count = 0;
            long mid = (min + max) / 2;
 
            for (int i = 0; i < k; i++) {
                count += arr[i] / mid;
            }
 
            /*
            길이의 최댓값을 구하고 반복문을 종료시킬 수 있는
            숫자 카드2에서 사용했던 upperBound를 이용하자.
             */
 
            if (count < n) {
                max = mid;
            } else {
                min = mid + 1;
            }
        }
        System.out.println(min - 1);
    }
}