Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

21. 이분 탐색

이분 탐색 알고리즘을 배워 봅시다.

Java / Python

3. 랜선 자르기

1654번

흔히 parametric search라고도 부르는, 이분 탐색을 응용하여 최솟값이나 최댓값을 찾는 테크닉을 배우는 문제

이번 문제는 K개의 랜선을 N개의 같은 길이의 랜선으로 잘라 만들 때, N개를 만들 수 있는 랜선의 최대 길이를 구하는 문제입니다.

• Java

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int K = sc.nextInt();
		long N = sc.nextLong();
		long[] arr = new long[K];
		long max = 0;
		for (int i = 0; i < K; i++) {
			arr[i] = sc.nextLong();
			max = Math.max(max, arr[i]);
		}

		long left = 1; // 랜선길이 = 자연수 / 최솟값 = 1
		long right = max;
		while (left <= right) {
			long mid = (left + right) / 2;
			long sum = 0;
			for (int i = 0; i < K; i++) { // 자른 개수 합
				sum += (arr[i] / mid);
			}
			if (sum >= N) { 
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		System.out.println(right);
	}
}

• Python

import sys
K, N = map(int, sys.stdin.readline().split())
lan = [int(sys.stdin.readline()) for _ in range(K)]
start, end = 1, max(lan) # 이분탐색 위치

while start <= end: 
    mid = (start + end) // 2 
    lines = 0 # 랜선 수
    for i in lan:
        lines += i // mid # 분할 된 랜선 수        
    if lines >= N:
        start = mid + 1
    else:
        end = mid - 1
print(end)