[C++][백준 1300] K번째 수

[문제]

1300번: K번째 수 (acmicpc.net)

1300번: K번째 수

---

[문제 풀이]

시간 초과와 메모리 제한으로 어떻게 접근해야 할지 한참을 헤맸다.

priority queue를 써서 풀려고 했으나 N * N 으로 모든 원소를 접근할려니 바로 시간초과가 날 수밖에 없었다.

 

하지만 2가지 정보를 알면 생각보다 쉽게 문제를 풀 수가 있다.

1. k이하의 숫자가 몇개가 있는지 파악을 해보자.

	1	2	3
1	1	2	3
2	2	4	6
3	3	4	9

 

3 * 3 의 테이블이 있을때 5 이하인 숫자들은 

	1	2	3
1	1	2	3	3
2	2	4	6	2
3	3	6	9	1

로 총 6개가 된다.

 

숫자 3 이하의 총 합을 파악해 보면

	1	2	3
1	1	2	3	3
2	2	4	6	1
3	3	6	9	1

 

로 총 5개가 된다.

즉 해당 행에서 min ( k / i , n ) 를 해보면 해당 행에서 k 값보다 작은 숫자들이 몇개가 있는지 파악이 가능하다.

 

2. 1번을 이용해서 1부터 N * N 까지 이분탐색을 해보자.

위에서 숫자 1 이하인 수는 1개가 있을 것이고 숫자 9 이하인 수는 9개가 있을 것이다. 3개 이하는 5개였으며 5개 이하는 6개였다.

이걸 정리해 보자면

 

숫자 n보다 작은 숫자의 개수

1	2	3	4	5	6	7	8	9
1	3	5	6	7	8	8	8	9

라는 값이 나올테고 이제 가장 작은 숫자를 파악해보자.

 

n번째로 작은 수

1	2	3	4	5	6	7	8	9
1	2	2	3	3	4	6	6	9

라는 값이 나온다.

 

이 2가지를 응용해서 봐보면 첫번째 표에서 두번째 줄에 있는 값이 k라고 가정을 하고 위의 값이 answer이라고 생각을 해보자.

그렇다면 k가 1일때 1이고 3일때 2 / 5일때 3 / 6일때 4 / 7일때 5 / 8일때 6 / 8일때 8 / 9일때 9가 된다.

즉, 위의 표와 아래의 표는 뒤집어서 생각을 해보면 비슷한 양식이 나온다.

 

왜 이럴까?

우리들은 k보다 작은 숫자의 개수를 구할 수가 있었다.

이는 반대로 말하자면 k번째로 작은 수가 무엇인지를 알 수가 있던 것이다.

즉, 해당 방식을 이용해서 문제를 풀어보도록 하자.

---

[코드]

#include<iostream>
#include <algorithm>

using namespace std;

long long array_sum(long long mid, int n){ // mid 값 이하의 숫자들이 몇개인지를 구하는 함수.
    long long answer = 0; //return을 할 값.

    for(int i = 1;i<=n;i++){ // 1부터 n까지 아래에서 위로 가자.
        if(n < (mid / i)){ // 만약 n 이 mid / i 보다 작다면 즉, n행이라는 범위를 넘어선다면
            answer += n; // n을 더해주자.
        }
        else{
            answer += (mid / i); //아니라면 mid / i 를 더해주자.
        }
        if(i > mid){ // 만약 i가 mid보다 커진다면 break를 하자.
            break;
        }
    }
    return answer;
}

int main(){
    long long n,k;
    cin>>n>>k;

    long long low = 1;
    long long high = n*n; //최댓값은 n * n 이다.
    long long mid = 0;
    long long answer = 0;
    while(low <= high){
        mid = (low + high) / 2;
        if(array_sum(mid,n) < k){ 
            low = mid + 1;
        }
        else{
            answer = mid;
            high = mid - 1;
        }
    }
    cout<<answer<<endl;

    return 0;
}

 

* 범위가 넓기 때문에 long long을 쓰는 것을 주의하도록 하자.