백준 1300번 K번째 수

문제 링크입니다: https://www.acmicpc.net/problem/1300

N이 최대 100,000이므로 브루트 포스 방식으로 진행하면 당연히 TLE가 나는 문제였습니다.

저는 욱제님(http://wookje.dance/2017/02/20/boj-1300-K%EB%B2%88%EC%A7%B8-%EC%88%98/) 포스팅을 참고하여 이분 탐색을 통해 풀 수 있었습니다.

알고리즘은 아래와 같습니다.

1. 임의의 숫자 mid를 골라 mid보다 작은 숫자의 개수를 파악해서 K 번째 숫자를 구합니다.

2. mid는 이분 탐색으로 통해 구하고 low=1, high=K로 시작합니다.

3. mid보다 작은 숫자를 효과적으로 구하기 위해 1 ~ N까지 반복문을 돌리고 i * j <= mid이므로 (mid / i)가 조건을 만족하는 j의 숫자입니다.

->하지만, N이 1000보다 크면 mid / i 가 N보다 커질 수 있으므로 mid/i 와 N 중 작은 값을 더해 mid보다 작은 숫자의 개수를 파악합니다.

4. 이분 탐색을 마치면 원하는 숫자를 구할 수 있습니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N, K;

        cin >> N >> K;

 

        int low = 1, high = K;

        int result = -1;

        while (low <= high)

        {

                 int cnt = 0;

                 int mid = (low + high) / 2;

                 for (int i = 1; i <= N; i++)

                         cnt += min(mid / i, N); //mid보다 작은 j의 수(i * j <= mid)

                 if (cnt < K)

                         low = mid + 1;

                 else

                 {

                         result = mid;

                         high = mid - 1;

                 }

        }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~