(1300) K번째 수

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

단계별로 풀어보기

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

 

 

 

이분 탐색인지 몰라서 어려운 문제 타입. k번째 수가 x라는 것은, 배열에 x보다 작거나 같은 수가 k개 이상 있다는 의미다.

이때 한 줄씩 탐색하면 i번째 줄의 숫자 중 x보다 작거나 같은 수는 min(N, x/i)이다.

또한 지금까지 파라메트릭 문제는 True에서 False로 바뀌는, 최댓값을 찾아야 하는 결정 문제였는데

이 문제는 반대로 False에서 True로 바뀌는, 최솟값을 찾아야 하는 결정 문제다.

따라서 결정함수 check가 x=lo일 때 False, x=hi일 때 True인 범위에서 탐색해야 한다.

이 부분도 개념에 대한 글을 쓸 때 따로 서술해야 할 정도로 미묘한 부분이긴 한데, 중요한 것은 인터넷에 찾아도 정말 다양한 형태가 나오므로 가장 본인에게 맞는 스타일을 찾는 것이 중요하다.

 

 

 

#include <iostream>
using namespace std;

int main() {
  int n, k;
  
  cin >> n >> k;
  
  int lo= 0, hi= 1000000000;
  
  while(lo+1<hi){
    int mid= (lo+hi+1)/2;
    long cnt= 0;
    
    for(int i=1;i<=n;i++)  cnt+= min(n, mid/i);
    
    (cnt>=k ? hi : lo)= mid;
  }
  
  cout << hi;
  
  return 0;
}