매개 변수 탐색(Parametric Search)

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

1654번: 랜선 자르기

백준 1654: 랜선 자르기 문제를 풀다가 어떻게 풀지 막막해서 알고리즘 분류를 봤더니 매개 변수 탐색이 있어 찾아보았다.

여러 블로그에서 도움을 얻어 이를 바탕으로 내가 이해한 방식으로 작성하고자 한다. (내가 이해한 것이니 타인이 보면 전혀 이해가 안 되는게 당연하다.)

 

매개변수 탐색을 하기위해 필요한 것.

내가 얻고 싶은 최소값인 시작값과 내가 얻고자 하는 최대값인 마지막값이 있다.

그리고 어디서 얻을지 필요한 배열 데이터가 있겠다.

 

그럼 최소값에서 최대값까지 반복을 한다는 것은 쉽게 알아차릴 것이다.

그럼 데이터들을 어떻게 다루느냐

여기서 이분탐색 알고리즘을 함께 쓴다.

 

이분탐색은 최소와 최대의 절반값을 비교하며 반복을 돌리는 알고리즘인데,

여기서 사용하는 절반값을 이용하여 내가 얻고자하는 데이터로부터 내가 원하는 결과를 도출할 수 있는지 없는지(boolean) 비교하며 중앙값을 시작값(start)에 넣을지 마지막값(end)에 넣을지 생각하면 된다.

 

자 그럼 어느정도 알고리즘은 파악이 된 거 같으니 문제를 풀자.

 

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

public class Main {

  static int need;
  static long max = 0;
  static int[] arr;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    int cnt = Integer.parseInt(st.nextToken());
    need = Integer.parseInt(st.nextToken());
    max = 0;
    long end = 0;
    arr = new int[cnt];
    for (int i = 0; i < cnt; i++) {
      arr[i] = Integer.parseInt(br.readLine());
      if (end<arr[i]) end = arr[i];
    }

    long start = 0;
    max = end;

    end++;
    // 이진 탐색
    while(start+1 < end){
      long mid = (start+end) / 2;
      if (checkCutting(mid)){
        start = mid;
      } else {
        end = mid;
      }
    }
    // 따로 저장했던 필요 개수 값 출력
    bw.write(max+"");
    bw.flush();
    bw.close();
    br.close();
  }

  // 매개 변수 탐색
  public static boolean checkCutting(long height){
    long sum = 0;
    for (int i = 0; i < arr.length; i++) {
      sum += arr[i]/height;
    }
    // 필요 개수가 합과 크거나 같으면 별도로 저장
    if (sum >= need) {
      max = height;
      return true;
    }
    else return false;
  }
}