이분탐색 - 백준 1300번 k번째 수✨

배워갈 것이 많아 보이므로 ✨ 별표

www.acmicpc.net/problem/1300

1300번: K번째 수

 

와 진짜 어렵다. 이게 왜 이분탐색이지?? 고민하다가 그냥 완전탐색을 이용해서 해보았다. 

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;

int main() {
	vector<int>b;
	b.push_back(0);
	int n;
	scanf("%d", &n);
	for (int i = 1; i < n + 1; i++) {
		for (int j = 1; j < n + 1; j++) {
			b.push_back(i * j);
		}
	}
	sort(b.begin(), b.end());
	int k;
	scanf("%d", &k);
	printf("%d" , b[k]);
}

이중 for문을 돌며 i*j를 배열에 다 넣고 정렬한 후 k번째를 출력하는 거다 역시나 메모리초과가 난다. 

누적합처럼 자기 자신보다 작은 개수를 가지고 이분탐색을 진행하면 될 거 같은데,,,,,,

자신보다 작은 개수를 어떻게 알지? 이게 가장 큰 고민이었다. 배열에 담으면 완전탐색이랑 다를 게 없다.

1시간을 고민하다 결국 다른 블로그들을 전전하며 해답을 찾아냈다 ㅜㅜ 

 

IDEA

1. K번째 수는 K보다 클 수 없다. 무조건 작거나 같다.  써보면 안다.

-> START = 1 , END = K로 둘 수 있다. 

 

2. 전체 행렬에서 M보다 작은 수(M번째 수 아님!)는 각 행에 대해서 M / 행 을 하면 개수가 나온다. 

진짜 신기하기도 하고 처음에는 이해가 안됐는데 곰곰히 생각해보면 맞다. 

근데 예를 들어 내가 찾는 수는 6인데 행령이 3X3 (N = 3)이라면 

1 2 3              첫번째 행에서 6 / 1 = 6 

2 4 6              두번째 행에서 6 / 2 = 3 

3 6 9              세번째 행에서 6 / 3 = 2

첫번째 행에 숫자가 3개밖에 없는데 6보다 작은 수가 6개가 나올 수 없다. 그렇기 때문에 정확하게는 

전체 행렬에서 M보다 작은 수의 개수는 각 행에 대해 min (N , M/행) 의 합이다. 

 

3. 만약 K보다 작은 수가 M개 존재한다면 K는 꼭 M번째 수가 아닌 M보다 더 작거나 큰 번째 수일수도 있다.

1,2,2,3,3,4,4,4,4,4,5가 있다할 때 7번째 수를 찾아보자.

7번째 수라고 하면 만약 4를 찾았을 때, 4보다 작거나 같은 수가 딱 7개가 있을거라고 생각하는데 착각이다. 

현재 4보다 작거나 같은 수는 10개다. 6번째부터 10번째까지 4이기 때문이다. 

 

 

예시 )) 

N = 3일때 7번째 수를 찾아보자. 

 

1) START = 1 , END = 7 , MID = 4이다. 

4보다 작은 수는 min (3 , 4/1) + min (3, 4/2) + min (3, 4/3) = 6이다. 

7보다 작으므로 4는 7번째 수가 아닐것이다. start 를 mid +1 로 옮겨준다. 

 

2) start = 5 , end = 7 , mid = 6이다.

6보다 작은 수는  min (3 , 6/1) + min (3, 6/2) + min (3, 6/3) = 8 이다. 

8은 7보다 크다. 6보다 작거나 같은 수가 8개 있단 뜻이기 때문에 6이 7번째 수인지 아닌지 확실하지 않지만 가능성은 있다. 그렇기 때문에 answer에 7을 저장해두고 우선 7보단 크니까 end = mid -1 =5가 된다. 

 

3) start = end = mid = 5

5보다 작은 수는 min (3 , 5/1) + min (3, 5/2) + min (3, 5/3) = 6이다. 

6도 7보다 작기때문에 숫자 5는 7번째 수가 될 수 없다. 

 

이후 start가 end보다 커지기 때문에 while문을 탈출하고 answer에 저장되어있던 6이 정답이 된다. 

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;

int main() {
	int n, k , answer;
	scanf("%d %d", &n, &k);
	int start = 1, end = k ;
	while (start <= end) {
		int mid = (start + end) / 2;
		int sum = 0;
		for (int i = 1; i <= n; i++) sum += min(n, mid / i);
		if (sum < k) start = mid + 1;
		else {
			end = mid - 1;
			answer = mid;
		}
	}
	printf("%d", answer);
}