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

 

 

처음에 어떻게 해야할지 막막한데

생각보다 센스있는 수 처리 방법이 있었습니다

 

이해 못 하다가 한 블로그 글을 보고 이해하게 되어

해당 블로그 글 링크를 같이 글 아래 쪽에 남깁니다

 

---

Solution

 

#include <iostream>

using namespace std;

int main() {
	int N, K;
	cin >> N >> K;
	int start = 1, end = K, ans = 0;
	while (start <= end) {
		int cnt = 0;
		int mid = (start + end) / 2;
		for (int i = 1; i < N + 1; i++) {
			cnt += min(mid / i, N);
		}
		if (cnt < K) {
			start = mid + 1;
		}
		else {
			end = mid - 1;
			ans = mid;
		}
	}

	cout << ans;
}

 

N=3, K=4이라 가정해보겠습니다.

그러면 1차원 배열로 나열해보면

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

이렇게 B 수열을 나타낼 수 있습니다

 

먼저 mid = 2 이므로cnt는 for문 이후 3이 됩니다

(즉, 2와 같거나 작은 수가 3개임을 알 수 있습니다)

 

그러면 저희는 4번째 수를 찾으므로

start를 mid + 1로 하고

 

start = 3, end = 4, mid = 3min(mid/i, N)에 의해

그 전에 있는 수들은 다 count 됩니다.

수행이 끝나면 cnt = 4로

K번째 수가 mid임을 확인할 수 있습니다.

mid 값을 이분 탐색 방법으로 계속 옮겨가며

앞에 있는 수가 몇 개인지 확인하는 알고리즘입니다

 

 

 

 

임의의 숫자 m을 골라서 K번째 숫자인지 판단해보자!

그 임의의 숫자 m은 무려 O(log K)에! 무려 이분 탐색으로 찾아보자!

그렇다면 떠오르는 질문, m 보다 작은 숫자의 개수를 어떻게 하면 빠르게 구할 수 있을까?

A[i][j]에서, i행에 속한 숫자들은 i*j이므로 모두 i의 배수이다.

그러므로 min(mid/i, N)이 i번째 행에서 mid보다 작은(= 임의의 m보다 작은) 숫자들의 개수가 된다.

eg. N = 1000인 경우, 첫 mid가 1000*1000/2 = 50만이 되는데,
50만/i가 N을 넘어갈 수 있으므로 min(mid/i, N)을 해준다.

조금 더 쉽게 쓰자면, i행의 숫자들은 i*1, i*2, i*3, ..., i*N으로 구성되어 있다.

i행의 숫자들 중 m보다 작거나 같은 숫자는 (i*j <= m)를 만족하는 j의 개수이고

이는 i*1, i*2, ..., i*j이므로, m/i와 같은 값이 된다.

각 O(log K)에 대해, 1부터 N까지 모든 i행에 대해 m/i를 수행해주어야 하므로

총 시간 복잡도는 O(NlogK)가 된다.

 

 

 

 

---

 

참고

 

아래 사이트를 보고 이해하는데 도움이 되었습니다

 

http://wookje.dance/2017/02/20/boj-1300-K%EB%B2%88%EC%A7%B8-%EC%88%98/