1300_K번째수

Concept & Idea

이 문제는 일단 배열을 사용하여 푸는 문제가 아니라는 점이다. 배열을 잡지 않고도 문제를 해결할 수 있고, 해결해야만 한다. ‘이분탐색을 어떻게 사용할 것인가’를 알아내는 것도 어려운 문제였다. 임의의 mid를 골라서, 해당 mid보다 작은 숫자의 갯수를 파악하여 K번째 수를 구한다. st는 1로 시작하고, end는 k로 끝나는데, 여기서 나는 N^2까지 돌아야 한다고 생각했었다. 왜 k까지 돌리는지는 증명을 통해 알아야내야 할 것 같다. N이 1000보다 커지게 되면, mid/i가 N보다 커질 수 있기 때문에 min(mid/i,N)을 한다.

Code

#include <iostream>
using namespace std;
int n,k;
int main(){
    cin>>n>>k;
    int st=1,en=k, mid, res;
    while(st<=en){
        mid = (st+en)/2;
        int cnt=0;
        for(int i=1; i<=n; i++)
            cnt+=min(mid/i, n);
        if(cnt<k) {
            st=mid+1;
        } else {
            en=mid-1;
            res=mid;
        }
    }
    cout<<res<<endl;
}

 

Fealing

왜 end가 K까지 돌아가야 하는건지가 의문이었다. 완벽하게 와닿지 않는 문제라서 나중에 한번 다시 풀어봐야 할 것 같다. 갯수를 세는데 일일히 가능한지 아닌지 보는것이 아니라 약수의 갯수를 확인하여 더해나가는 것이 중요한 방식인 것 같다.