(1654) 랜선 자르기

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

단계별로 풀어보기

25단계(이분 탐색) 3번째

 

 

 

이분 탐색과 자주 같이 쓰이는 파라메트릭 서치가 필요한 문제다.

파라메트릭 서치란 최적화 문제를 결정 문제로 바꾼 뒤 최적해를 구하는 알고리즘이다.

최적화 문제란 최댓값, 최솟값 등 조건을 만족하는 최적의 값을 구하는 문제고, 결정 문제는 답이 Y/N으로 나뉘는 문제를 의미한다.

 

가능한 랜선 길이의 최댓값을 구하라(최적화 문제)를 길이가 x인 랜선 N개를 만들 수 있는가?(결정 문제)로 바꿔 보자.

이때 결정 문제의 답은 x가 증가함에 따라 Y였다가 어느 순간을 기점으로 N으로 바뀔 것이다. 이렇게 답이 바뀌는 지점이 하나라면(답의 구간이 두 개라면) 이 결정문제는 이분적이다라고 하고, 이분 탐색을 이용해 경계 지점을 찾아낼 수 있다.

길이 x인 랜선을 N개 만들 수 있다면 길이를 더 늘릴 수도 있으므로 x이상 범위에서 다시 탐색하고, 만들 수 없다면 x미만 범위에서 다시 탐색한다. 가능한 정답의 범위는 무려 1이상 2^31미만이지만, 이분 탐색을 이용하면 O(log N)의 시간이 소요되므로 많아야 30번 내외의 계산으로 정답을 찾을 수 있다.

 

실제로 이분 탐색은 lo와 hi의 범위, while 내 조건문, 결정 조건이 끝난 뒤 구간을 좁히는 방법 등의 세세한 부분에서 헷갈리는 경우가 많아 이 부분을 확실하게 잡고 가는 것이 중요하지만, 여기서는 생략한다. 본인에게 가장 잘 맞는 스타일을 찾는 것이 중요하다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;
typedef unsigned int ui;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int k, n;
  
  cin >> k >> n;
  
  vector<ui> v(k);
  
  for(int i=0;i<k;i++)  cin >> v[i];
  
  ui lo= 1, hi= 2147483648;
  
  while(lo+1<hi){
    ui mid= (lo+hi)/2, cnt= 0;
    
    for(int i=0;i<k;i++)  cnt+= v[i]/mid;
    
    (cnt>=n ? lo : hi)= mid;
  }
  
  cout << lo;
  
  return 0;
}