1300 - K번째 수

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

1300번: K번째 수

이 문제는 단계별로 풀어보기의 '이분탐색'에 포함된 문제이다.

굉장히 신기한 문제였기에 그만 구글링의 힘을 빌리고야만 문제다.

부끄럽지만 찬란한 제출 현황을 공개하면서 내가 구글링을 한 이유에 대해 조금이나마 변명해 보겠다.

 

맞왜틀 9번했다 껄껄 (6번은 실수지만)

 

알고리즘

이 문제에서 구하고자 하는 것은 'K번째 수'이다.

우리가 알 수 있는 것은 1~n*n까지의 값이 존재 할 것이고, k번째 수의 값은 그 사이에 위치 할 것이라는 사실이다.

따라서 우리들은 k번째 수인, 1~n*n 사이의 미지수 X를 찾아야 한다.

 

그렇다면 미지수 X와 k의 관계를 살펴보자. 미지수 X 보다 같거나 작은 값을 가진 숫자의 개수는 k보다 같거나 클 것이다. 왜냐하면 k번째 수는 미지수 X이기 때문이다. 따라서 우리들은 같거나 작은 수들을 기준으로 이진 탐색하면 된다.

 

그렇다면 이제는 어떻게 미지수 X보다 같거나 작은 값을 가진 숫자의 개수를 구할 수 있을지 생각해야한다. 

그 방법을 알기위해서는 먼저 기존의 데이터가 메트릭스의 row와 col을 이용해 값을 정했다는 것을 상기해야한다. 아래 예시를 보면서 왜 상기를 해야하는지 설명하겠다.

 

1*1	1*2	1*3
2*1	2*2	2*3
3*1	3*2	3*3

위의 3 X 3 메트릭스를 row별로 분석해 보자. 첫번째 줄은 1*col, 두번째 줄은 2*col, 세번째 줄은 3*col이다. 감이오나요?

이때 각 row의 값들을 X와 어떻게 비교를 해야 X보다 같거나 작은 숫자의 개수를 구할 수 있을까?

 

그 방법은 다음과 같다.

각 row에서 X보다 작은 것의 개수는 X/row와 n(size)중에 작은 값을 택하는 것이다.

 

자세히 하나하나 따져보자.

 

먼저 col을 기준으로 생각해보면, 모든 row에서 각 칸의 값은 row * col의 결과이다. 따라서 row별로 따져 볼때 X보다 작은 수의 개수는 X/row보다 작은 col의 개수이다. (물론 X/row가 n보다 크다면 해당 row의 모든 row * col이 X보다 작다는 뜻이므로 n개가 X보다 작다고 할 수 있다.)

 

따라서 우리들은 X보다 같거나 작은 수를 구하려고 할 때, 1~n까지 모든 row에 대해 min(X/row, n)의 합을 계산하면 된다.

이에 따라 시간 복잡도는 이진 탐색까지 O(NlogN)이 된다는 것을 알 수 있다.

 

 

코드는 다음과 같다.

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
typedef unsigned long long ull;
 
ull countSmall(ull value, ull size) {
    ull result = 0;
    for (int i = 1; i <= size && i <= value; ++i) {
        result += min(value / i, size);
    }
    return result;
}
 
ull search(ull size, ull k) {
    ull minVal = 1, maxVal = size * size;
 
    while (minVal <= maxVal) {
        ull midVal = (minVal + maxVal) / 2;
        ull counts = countSmall(midVal, size);
        if (counts < k) {
            minVal = midVal + 1;
        }
        else {
            maxVal = midVal - 1;
        }
    }
 
    return minVal;
}
 
int main(void) {
    ull size, k;
    cin >> size >> k;
    cout << search(size, k);
 
    return 0;
}

 

신기한점

아마 많은 분들이 만났을 문제이다.

이 문제는 쓸데없는 if문 하나, 연산하나가 시간 초과 오류를 발생시킨다. 이미 탈모인데 정말 머리빠지는 줄 알았다.

이분께서 해답을 주셨는데, if문 하나를 제거 했더니 금방 통과했다. 허허 굉장히 신기한 문제다.

혹시 이 문제를 풀면서 시간초과 에러를 만났다면 쓸데 없는 if문 하나를 제거해보자.

 

위의 이분의 블로그 주소

https://fullalgorithmpanic.blogspot.com/2016/09/boj-1300-k.html

 

글을 쓰는데 도움을 주신분

갓갓 풀스택 MayLeaf님 감사합니다.