랜선 자르기 ( 백준 1654 )

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

 

* 이분탐색을 기반으로한 Parametric Search 알고리즘 활용하는 문제.

* 범위는 전선 길이는 1부터 시작하니 left는 1로 설정하고, right는 주어진 전선 길이중에 제일 긴 전선을 선택한다.

* Binary Search는 찾아야 하는 값이 mid 값보다 크면 left = mid+1 해주었지만 위 문제는 잘라야할 길이를 결정해주어야 한다

 

잘라야할 범위 설정

 

- mid 값으로 각각의 전선을 자르면서 최종 잘려져야할 케이블 갯수를 Binary Search로 탐색하는 것이다.

- 위 같은 Parametric Search는 한번 탐색한 mid 값은 탐색하지 않아야 하기 때문에 (mid+1) 과 (mid-1) 양옆을 탐색한다.

- while() 조건도 left<= right 과 같이 같다는 조건을 넣어줘야 한다.

 

import java.io.*;
import java.util.*;

public class BOJ1654 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int size = Integer.parseInt(st.nextToken());
        int target = Integer.parseInt(st.nextToken());
        int max = Integer.MIN_VALUE;
        int[] cable = new int[size];
        for(int i = 0; i < size; i++) {
            cable[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, cable[i]);
        }
        System.out.println(pSearch(cable, target, max));
    }
    private static long pSearch(int[] cable, int target, int max) {
        long left = 0, right = max, result = 0;
        while(left < right) {
            long mid = (left + right) / 2;
            // 더 잘렸으면 true 반환
            if (decision(cable, target, mid)) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return result;
    }
    private static boolean decision(int[] cable, int target, long mid) {
        long curLine = 0;
        for(int line : cable) {
            curLine += (line/mid);
        }
        return curLine >= target;
    }
}