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

 

 

지금까지 정렬 문제를 풀어봤는데 오늘부터 이분 탐색 문제를 풀어보려고 한다.

 

 

 

문제 1300번

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

1300번: K번째 수

 

처음에는 벡터를 이용하여 풀어볼까 했는데 뭔가 어려운 느낌이 들어서 찾아보니 이런 식으로 푼 분도 있었다.

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

int main() {
	int n,k;
	cin >> n >> k;

	int start = 1;
	int end = k;
	while (start < end) {
		int mid = (start + end) / 2;
		int cnt = 0;

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

		if (cnt < k) {
			start = mid + 1;
		}else {
			end = mid;
		}
	}

	cout << end << '\n';
	
}

 

이분탐색을 하여 찾으려고 하는 인덱스 값보다 작으면 start를 중간값+1 해주고 아니면 end를 mid로 해줬다. 

cnt는 mid보다 작거나 값은 값이다.

 

[참고] https://velog.io/@murraiya/%EB%B0%B1%EC%A4%80

 

 

 

뭔가 어려워서 내일 다시 한번 풀어봐야겠다.

오늘도 너무 졸리다...