백준 1300 K번째 수 (C++)

1300번: K번째 수

이분 탐색을 이용한 아이디어가 필요한 문제이다. 먼저 N=5 일때의 표를 한번 보자.

	1	2	3	4	5
1	1	2	3	4	5
2	2	4	6	8	10
3	3	6	9	12	15
4	4	8	12	16	20
5	5	10	15	20	25

만약 r=4라고 할때, 1행부터 차례대로 r보다 작거나 같은 값의 갯수는 4,2,1,1,0이다. 이는 min(mid/i, N)으로 나타낼 수 있다. 즉 반복문을 돌렸을때 r보다 작은 값들의 갯수가 k와 같은 경우를 찾으면 된다. 이제 r을 구해야 하는데 이는 이분 탐색으로 구해주었다. r은 항상 k보다 작거나 같기때문에 1을 시작, k를 끝으로 지정해주고 mid를 구해 해당 값보다 작은 수의 갯수를 구해주며 result를 구했다.
굉장히 어려웠던 문제였다. 처음 아이디어를 잘못 생각해 시간을 많이 날렸고 블로그를 참고했을 때도 이해하기가 어려웠었다... 이번 문제의 키포인트는 이분 탐색이 아니라 사실상 구현 아이디어 였다고 생각한다. 많은 문제들을 풀어봐야 겠다...

---

#include <iostream>
#include <algorithm>

using namespace std;

int N, k, result = 0;

void solution() {
	int s = 1, e = k;


	while (s <= e) {
		int mid = (s + e) / 2;
		int cnt = 0;

		for (int i = 1; i <= N; i++) {
			cnt += min(mid / i, N);
		}

		if (cnt < k) {
			s = mid + 1;
		}
		else {
			e = mid - 1;
			result = mid;
		}
	}
	
	cout << result;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;
	cin >> k;

	solution();
	
	return 0;
}