1300번-K번째 수

문제

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

1300번: K번째 수

---

접근방법

개인적으로 탐색 기준을 무엇으로 잡아야 할 지 정말 많은 고민을 한 문제이다. 이분 탐색 문제들을 모아 놓은 카테고리에서 문제를 고른거라풀었지 아니었으면 절대 못 풀었을거 같다. (알고 풀어도 너무 어려웠음)

문제에서 주어지는 n의 크기 때문에 완전탐색으로는 시간초과가 발생하는 문제이기 때문에 시간복잡도를 줄여야만 하는 문제였다.

이 문제의 탐색 기준은 "임의의 숫자 mid값이 K보다 많거나 같은 경우"이다. 문제의 탐색 기준이 안 와닿아서 풀기가 어려운 문제이다.

위와 같은 기준은 이차원 배열의 구현되는 성질을 보면 알 수 있다. 밑에 n = 4인 경우의 표를 보자

1	2	3	4
2	4	6	8
3	6	9	12
4	8	12	16

이 때 임의의 mid값보다 작은 경우의 cnt갯수를 세주면 mid값 앞에는 적어도 앞에 cnt 개가 앞에 있다는 것이다.

예시를 들어보자

배열 a에 1 2 3 4 5 6 7 8 9 가 앞에 있고 내가 4번째 수를 찾는다고 가정할 때 mid값을 4라고 가정하면 a에 mid 값보다 작은 경우는 1,2,3,4가 있으므로 답은 4이다.

즉 mid값보다 작은 경우의 수들이 k개 있을 경우 k의 위치라는 의미이다.

그러면 배열을 구성하면 시간초과가 나오는데 어떻게 갯수를 세라는지 의문이 든다.

정답코드에서 26번째 줄 코드를 보면 min(mid/i, n)이라는 코드가 보인다 의미는

 

i번째줄에서 mid값보다 작은 경우의 수를 더한다. 만약 mid/i의 수가 한 줄을 의미하는 n보다 클 경우 n개를 더해준다.

mid/i는 i번째 줄마다 i의 간격으로 건너뛰기 때문에 i번째 줄에 mid보다 작은 값들은 mid / i 로 구해진다.

 

로 이해하면 된다.

---

정답코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
 
int main(void)
{
    fastio;
    int n, k;
    cin >> n >> k;
 
    int left = 1;
    int right = k;
 
    while(left + 1 < right)
    {
        int cnt = 0;
        int mid = (left + right) / 2;
        for(int i = 1; i <= n; i++)
            cnt += min(mid/i, n);
        if(cnt >= k)
            right = mid;
        else
            left = mid;
    }
    cout << right << "\n";
}