[백준] 알고리즘 C++ 1300번 - K번째 수문제

문제

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

1300번: K번째 수

소스코드

/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <iostream>
#include <algorithm>
using namespace std;
long long n,k;
long long ans;
void bs(){
    long long s=1;
    long long e=n*n;
    while(s<=e){
        long long mid=(s+e)/2;
        long long cnt=0;
        for(int i=1;i<=n;i++){
            cnt+=min(mid/i,n);
        }
        if(cnt<k){
            s=mid+1;
        }
        else{
            ans=mid;
            e=mid-1;
        }
    }
}
int main()
{
    cin>>n>>k;
    bs();
    cout<<ans;
    return 0;
}

해설

배열 자체를 선언해서 모든 수를 i*j 수를 넣은 후에 일차원 배열로 넣은 후, 정렬해서 답을 도출하는게 가장 단순한 문제이다.

하지만 배열자체를 선언할 수 없을뿐더러(선언 값이 너무크다.) 시간적인 부분도 고려할 수 없기에 이문제는 다른 접근방법이 필요하다.

K번째 수를 찾는다? 어떤 값 s라고 두었을 때 s가 k번째 수라고 가정하면 s보다 작은 수들의 개수는 k개가 있을 것이다.

결국 초점을 k번째 숫자를 찾는다고 생각하지말고, 임의의 수 s(즉 미드값)보다 작은 수들의 개수와 k를 비교해보는 것이다.

그렇다면 이런 유형의 문제는 이분탐색으로 해결가능하다.

S보다 작은 수들의 개수가 k보다 작다면 스타트지점을 높게 잡아서 좀 더 많은 개수를 셀 수 있게 해준다.

반대로 개수가 k보다 크다면 마지막지점을 줄여서 개수를 줄여본다.

그렇다면 s보다 작은 수들의 개수는 어떻게 구할지가 가장 큰 핵심이 되겠다.

 

N=5 라고 가정해보자.

 

1  | 1 2 3 4 5 

2 | 2 4 6 8 10

3 | 3 6 9 12 15

4 | 4 8 12 16 20

5 | 5 10 15 20 25

 

어떻게 구할지 모를때는 분명 간소화 시킬 수 있는 공식을 도출해낼 수 있다고 생각하고 몇가지 수를 대입해보면된다.

먼저 s=2라고 가정하면 n의 배열에서 2보다 작은 숫자들의 개수를 셀 수 있다.

2인경우 i번째 부터 n까지 행렬에서 순서대로 2,1,0,0,0

3인 경우 순서대로 3,1,1,0,0

4인 경우 순서대로 4,2,1,0,0

즉 s보다 작거나 같은 수들의 개수는 cnt=min(s/i,n)이 되게된다.

N과 s/i를 비교하는 이유는 배열 n보다 초과한 값이 최소의 개수로 들어갈 수 있기 때문에 n과 함께 비교해주어야 한다.