백준 1654 랜선 자르기 JAVA

문제

https://www.acmicpc.net/problem/1654

---

입출력

---

예제

---

태그

• 이분 탐색
• 매개 변수 탐색

---

풀이

• 이분탐색을 이용한 풀이
• left=0, right=주어진 랜선 길이 중 가장 큰 값
• 문제에서 랜선의 길이가 2^31-1 이하의 굉장히 큰 수이므로 long을 사용한다.

• 50%에서 틀린이유)
• 예를 들어 주어진 랜선 길이가 1 1, 총 2개일 경우
• left=0, right=1이 된다.
• mid = (0+1)/2 = 0으로 이분탐색시 (랜선길이 / mid) 에서 0으로 나누는 꼴이 된다.
  -> right의 값을 1 늘려준 상태에서 이분탐색을 진행한다.(right++)

---

코드

정답 코드

/**
 * 1654_랜선 자르기
 *
 * 이분탐색을 이용한 풀이
 * left=0, right=주어진 랜선 길이 중 가장 큰 값
 *
 * 50%에서 틀린이유)
 * 예를 들어 주어진 랜선 길이가 1 1, 총 2개일 경우
 * left=0, right=1이 된다.
 * mid = (0+1)/2 = 0으로 주어진 랜선길이 / mid 에서 0으로 나누는 꼴이 된다.
 * -> right의 값을 1 늘려준 상태에서 이분탐색을 진행한다.(right++)
 */

public class P_1654 {
    static int K, N;
    static Long[] line; // K개의 랜선 길이를 담는 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        K = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        long right = 0L;
        line = new Long[K];
        for (int i = 0; i < K; i++) {
            line[i] = Long.parseLong(br.readLine());
            right = Math.max(right, line[i]);
        }
        right++; // 위의 주석 참고

        long left = 0L;

        // 이분탐색 진행
        while (left < right) {
            long mid = (left + right) / 2;
            long cnt = 0L;

            for (int i = 0; i < K; i++) {
                cnt += (line[i] / mid);
            }

            if (cnt < N) {
                right = mid;
            }
            else {
                left = mid + 1;
            }
        }

        System.out.println(left -1);
    }
}