[백준] 1654 랜선 자르기

www.acmicpc.net/problem/1654

1654번: 랜선 자르기

2021-01-12

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main1654 {
    public static int N, K;;
    public static long arr[], answer;
    
    public static boolean check(long num) {
        int count = 0;
        for(int i = 0; i < K; i++) {
            count += (arr[i] / num);
        }
        
        if(count >= N) {
            answer = num;
            return true;
        }
        
        return false;
    }
    
    public static void solve() { 
        long left = 1;
        long right = arr[K/2];
        long mid = (left+right)/2;
        
        while(left <= right) {
            if(!check(mid)) {
                right = mid-1;
            } else {
                left = mid+1;
            }
            mid = (left+right)/2;
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine().trim());
        K = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        arr = new long[K];
        for(int i = 0; i < K; i++) {
            st = new StringTokenizer(bf.readLine().trim());
            arr[i] = Integer.parseInt(st.nextToken());
        }
        answer = 0;
        Arrays.sort(arr);
        solve();
        System.out.println(answer);
    }
}
 

 

#문제풀이

파라매트릭 서치(Parametric Search)로 푼 문제이다. 

 

1. K개의 값을 오름차순으로 정렬 한 후 중간 값을 선택한다.

 

2. 선택한 중간값을 1~중간값으로 보고 이분탐색으로 선택할 수 있는 숫자를 정한다. 

 

3. 그 숫자가 K개의 값을 다 돌면서 N개 이상의 랜선을 채울 수 있다면, left값을 mid+1로 옮기고 아니라면 right 값을 mid-1로 옮겨서 범위를 좁혔다.