백준 1300_K번째 수

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

 

 

이 문제를 풀 때 N의 최댓값이 10^5 이므로 이차원 배열(N x N)을 만들어 문제를 풀면 

100억의 메모리가 필요하고, 10^10(log(10^10)) 의 시간이 필요한데 사실상 불가능하다.

메모리
O(N^2)

시간
O(N^2 log(N^2))

 

 

이 문제에서 요구하는 것은 

"정렬된 배열에서 k번째로 작은 값"

이다.

 

만약 어떤 값 x를 기준으로 배열(B) 에서 x 이하의 원소가 몇 개인지만 구하면 

 

• “x 이하가 k개 이상이면 → B[k]는 x 이하여야 함”
• “x 이하가 k개 미만이면 → B[k]는 x 보다 커야 함”

위와 같은 기준을 얻을 수 있고, 이분탐색을 이용해 원하는 B[k]를 빠르게 구할 수 있다.

 

 

 

문제를 보면 이론상으론

1 <= B[k] <= N * N

이지만, 사실 B[k]는 k보다 커질 수 없다. (배열을 직접 그려보면 더 쉽게 알 수 있다..)

 

따라서, 이분 탐색의 시작 범위를 1, 마지막 범위를 k로 설정하고 이분탐색을 진행한다.

 

#include <algorithm>
#include <iostream>
#include <vector>

int main(void) {
  std::ios::sync_with_stdio(false);
  std::cin.tie(NULL);
  std::cout.tie(NULL);

  int N, K;
  std::cin >> N >> K;

  int start = 1;
  int end = K;
  int ans = 0;

  while (start <= end) {
    int mid = (start + end) / 2;

    long long sum = 0;
    for (int i = 1; i <= N; i++) {
      sum += std::min(mid / i, N);
    }

    if (sum < K)
      start = mid + 1;
    else {
      end = mid - 1;
      ans = mid;
    }
  }
  std::cout << start << '\n';

  return 0;
}

 

이분 탐색으로 문제를 풀어야겠다는 생각하기까지가 어려운 문제였던 것 같다.