1300번 : K번째 수 [C++]

 

문제 링크

성공 여부(걸린 시간): 2시간 (실패)

아이디어

1. 실패한 방법 : K를 최대한 줄여서 탐색하자!

처음에 내가 생각한 것은 이분 탐색으로 k번째 수를 찾아내는 것이 아니라 

만약에 N = 4이고 K가 10이라면 

K보다 lower bound인 i*2값을 만족하는 i값을 이분탐색으로 찾았다.

그렇게 하면

이런식으로 구할 수 있는데 

그럼 나머지 지점에 대해서만 탐색해서 출력해주면 되겠다는 생각을 했다.

하지만 해당 범위에 속한 값의 개수를 구하는데에 힘든 상황들이 존재했고

뭔가 나머지 지점에 대한 탐색이 지금 예시로 든 것은 N=4이기에 금방하지만

N이 10만일때는 시간이 상당히 많이 소요될 것으로 생각이 들었다.

 

2. 성공 방법 : 1~N*N 사이의 수를 이분탐색으로 A[i][j] = i × j를 활용해서 해당 수보다 작은 수를 카운팅해서 구하기

내가 너무 어렵게 생각했나 싶기도 했는데 해당 방법을 보고나니 약간의 현타도 왔으나

나름 또 접근하긴 했다는 생각을 하게 되었다.

 

이 방법은 이분탐색으로 우선 K번째의 수를 구하는 것인데 mid가 K번째의 수가 된다.

해당 수가 K번째인지 아닌지 알기 위해서 매 mid값의 갱신마다 

for (ll i = 1; i <= N; i++) {
	cnt += min(N, mid / i);
}

 

이렇게 해당 mid값보다 작은 수를 카운트 해준다.

mid / i는 뭐냐? 

 

A[i][j] = i × j 인데 

mid = i * j일때

mid / i = j이고

j 만큼 더해주는데 만약 j가 N보다 크다면 최대치는 N개로 제한해서더해주면 된다.

 

그러고 주의할점이 하나 있다.

 

그것은 바로 cnt==K일때 멈추면 안됨.

cnt(mid) ≥ K 를 만족하는 가장 작은 mid를 구해야 하기 때문임.

풀이코드

#include<iostream>
#include<algorithm>
using namespace std;
long long typedef ll;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll N, K;
    cin >> N;
    cin >> K;
    ll left = 1;
    ll right = N * N;
    ll mid = (left + right) / 2;
    ll answer = 0;
    while (left <= right) {
        ll cnt = 0;
        mid = (left + right) / 2;
        for (ll i = 1; i <= N; i++) {
            cnt += min(N, mid / i);
        }
        if (cnt >= K) {
            answer = mid;
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    cout << answer;
    return 0;
}