Beakjoon] K번째 수 (백준 1300 코테) - 탐색

---

🅰️문제주소 : https://www.acmicpc.net/problem/1300

1300번: K번째 수

 

🚩문제 

 

 

🪡풀이 

 - 문제 그대로 2차원 배열을 만들고 정렬을 시키면 시간복잡도가 N^2으로 초과해버린다.
 - A[i][j] = i×j 배열에서 두 가지의 규칙을 찾아야 한다.
  1) 해당배열은 k번째 값은 k의 값을 넘지 못한다. (3x3배열에서 마지막 인덱스의 값이 9이므로)
  2) 한 행에서 '중앙값을 행으로 나눈 값' vs '열의 수' 둘 중 작은 수는 해당 행에서 중앙값보다 작거나 같은 수의 개수가 된다. 따라서 이 값을 모든 행에서 구한 뒤 합산한 뒤 K와 비교하면 K번째 값이 현재보다 앞쪽에 있는지, 뒤쪽에 있는지 알 수 있다. 
 - 위 규칙에 의해서 '작거나 같은 수의 개수'의 합 값이 K보다 작으면 K값은 더 뒷쪽에 있으므로 시작인덱스 값을 중앙값+1으로 변경한다.
 - 반대로 '작거나 같은 수의 개수'의 합이 K보다 크거나 같으면 현재 K의 값을 찼았거나 K의 값이 더 앞쪽에 있다는 뜻이므로 임시로 정답에 중앙값을 넣어준 뒤 종료인덱스를 중앙값-1로 변경하고 이진탐색이 종료될 때까지 계속한다. 

 

☕코드는 아래 숨김

#include <iostream>
#include <vector>
#include <math.h>
int main() {
	std::ios::sync_with_stdio(false);
	std::cout.tie(0);
	std::cin.tie(0);

	int N, k;

	std::cin >> N;
	std::cin >> k;

	int start = 1;
	int end = k;
	int result = 0;
	while (start <= end) {
		int mid = (start + end) / 2;
		int temp_sum =0;
		for (int i = 1; i <= N; ++i) {
			temp_sum += std::min(N, mid / i);
		}
		if (temp_sum < k) {
			start = mid + 1;
		}
		else {
			result = mid;
			end = mid - 1;
		}
	}

	std::cout << result;

	return 0;
}

 

💡알게 된 것 

 - A[i][j] = i×j 배열에서 두 가지의 규칙
  1) 해당배열은 k번째 값은 k의 값을 넘지 못한다. (3x3배열에서 마지막 인덱스의 값이 9이므로)
  2) 한 행에서 '중앙값을 행으로 나눈 값' vs '열의 수' 둘 중 작은 수는 해당 행에서 중앙값보다 작거나 같은 수의 개수가 된다. 따라서 이 값을 모든 행에서 구한 뒤 합산한 뒤 K와 비교하면 K번째 값이 현재보다 앞쪽에 있는지, 뒤쪽에 있는지 알 수 있다. 

이걸 모르면 탐색이고 뭐고 시작도 할 수 없다...

---