[PS] 백준 1300번: K번째 수

|

문제

내가 이해한 문제 내용

2차원 배열의 값들이 i*j 형태로 주어지고 1차원 배열에 정렬할 경우의 $K$번째 수를 구하여라.

접근 방식

처음에 이분탐색일거라는 생각을 못해서 그냥 인덱스로 푸는 것을 계속 고민했다. 한 3시간쯤 고민한 후에 풀이를 보게 되었고 i*ji의 배수라는 점에 착안하여 이분탐색을 진행하면 된다는 것을 알았다.

  • $N=4$, $K=6$일 경우
  • 최솟값인 1과 최댓값인 16을 양 끝으로 이분탐색을 진행한다.
  • 중간값인 8을 구한 후에 각 행에서 중간값 이하의 숫자들이 몇개 있는지 계산한다. 이 때 i로 나누게 되는데 $N$보다 커질 수가 있으므로 min(8/i, 4)으로 계산한다.
    • 1행에선 4 이하의 값들이 4개
    • 2행에선 4 이하의 값들이 2개
    • 3행에선 4 이하의 값들이 1개
    • 4행에선 없으므로 총 6개
  • 계산한 값과 $K$를 비교하면 같기 때문에 빠져나온다.

어려웠던 점 & 배운 점

이분탐색인 걸 알아도 i*j를 배수라는 관점에서 보지 못하면 풀기가 어려운 문제이다. 어떤 걸 찾으라는 문제에선 항상 이분탐색을 고려하도록 하자.

원래 처음 풀었을 때는 해당 숫자가 i*j로 나올 수 있는 값인지 확인했는데 다른 분들의 풀이를 보니 이분탐색을 끝까지 해서 정당성을 이끌어냈다. 즉, i==j까지 반복하고 끝내는데 그 안에서 i*j보다 크면서 $K$개의 수가 있을 경우 줄이게 되므로 반드시 i*j로 계산할 수 있는 값이 답이 된다.

아래 코드는 dotorya님 코드를 참고한 것으로 중간값 이하의 숫자개수들이 $K$보다 작을 경우 중간값을 증가시키는데 이 때 중간값을 저장해두어 이분탐색이 종료되었을 때 답으로 이용하는 방법이다. 종료 직전에 i==j일테니까 미리 그 값을 저장하는 것.

시간복잡도

$O(NlgN^2)$인데 $O(NlgK)$ 풀이도 있다.

코드

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;
ll n,k,l,r,m,cnt,ans;

int main(void)
{
    scanf("%d%d",&n,&k);

    l=1,r=n*n;
    while(l<=r){
        m = (l+r)/2;
        cnt = 0;
        for(ll i=1; i<=n; i++)
            cnt += min(m/i,n);

        if(cnt<k){
            ans = m;
            l = m+1;
        } else r = m-1;
    }
    

    printf("%lld",ans+1);
    return 0;
}