[JAVA/알고리즘] 매개 변수 탐색 (백준 1654)

매개 변수 탐색이란, 

최적화 문제 (어떤 알고리즘의 최적 솔루션을 찾는 것)를 결정 문제 (답이 이미 정해져 있다고 보고 문제 풀기) 로 풀 수 있는 알고리즘

 

조건에 만족하는 최대값, 최소값을 찾는 문제.

 

시간 복잡도 : O(logN)

 

 

1. 매개 변수 : 검사 범위 (start, end)의 중간값.

2. 결정 함수 : 조건을 만족하면 true 만족하지 않으면 false 반환. 반환값에 따라 범위를 조정. 

 

 

원하는 값을 찾았을 때, 

이진 탐색: 원하는 값의 위치를 반환 후 종료

매개 변수 탐색 : 살펴볼 범위가 없을 때 까지 반복

---

[백준 1654] 랜선 자르기

이 문제는 조건 (기존의 K개의 랜선으로 N개 이상의 랜선을 만드는 것)을 만족하는 최대의 랜선 길이를 구하는 문제이다. 

 

따라서, 

매개 변수: "최대 랜선의 길이"

결정 함수: 입력 받은 K개의 랜선 배열 (arr)의 순환하여 랜선의 개수(cnt)를 구할 때,  N개의 랜선을 만들 수 있는지 

 

이 때,

cnt 값이 크다는 것은 랜선의 길이가 짧다는 의미이므로

cnt >= N 이면 start = mid + 1

cnt < N 이면 end = mid - 1 로 범위를 변경하여 start와 end가 교차되는 순간(start > end)까지 반복한다. 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int k = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        long[] arr = new long[k];
        for(int i=0; i<k; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);

        long start = 1;
        long end = arr[k-1];
        while (start <= end) {
            int cnt = 0;
            long mid = (start + end) / 2;
            for (int i=0; i<k; i++) {
                cnt += arr[i] / mid;
            }

            if (cnt >= n) {
                start = mid + 1;
            }
            else {
                end = mid - 1;
            }
        }
        System.out.println(end);
    }
}

*) 주어진 랜선의 길이가 2^31 - 1 보다 작거나 같은 자연수이므로 int형이 아닌 long형을 사용해야 한다.