백준 1654번 : 랜선 자르기(Java)

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

1654번: 랜선 자르기

---

[풀이]

• 이분탐색 유형의 문제였습니다.
• 이분탐색의 start , end 변수에서 start 변수는 1부터 시작합니다.
• 해당하는 수를 찾기 보다, 최대 개수를 구하는 것이기 때문에 이분탐색의 while문 내부에서 for문으로 자른 랜선의 개수 변수를 이용하여 N 변수와 비교해야 합니다.
  • 개수가 N보다 작다면, end변수에 mid -1 값을, N보다 커서 유효한 답이면 start변수에 mid + 1의 값을 할당하며 탐색 과정을 반복합니다.
• int 형의 크기를 벗어나기 때문에 long 타입을 사용해야 합니다.

---

[코드]

 

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

public class Main {
    static int K, N;
    static long[] arr;

    public static long solve(long start, long end) {
        long result = 0;
        long count = 0;
        while (start <= end) {
            long mid = (start + end) / 2;
            count = 0;
            for (int i = 0; i < K; i++) {
                if (arr[i] >= mid) {
                    count += (arr[i] / mid);
                }
            }

            if (count < N) {
                end = mid - 1;
            } else {
                result = mid;
                start = mid + 1;
            }
        }
        return result;
    }

    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());
        arr = new long[K];
        for (int i = 0; i < K; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);
        long result = solve(1, arr[K - 1]);

        System.out.println(result);
    }
}