[백준] 1300 K번째 수

⚡백준 1300 K번째 수

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

풀이

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

typedef unsigned long long ull;

ull n, k;

//결정 문제: 숫자 x앞에 k개 혹은 k개 이상의 숫자가 존재하는가?

bool decision(int x) {
	ull cnt = 0;
	for (ull i = 1; i <= n; ++i)
		cnt += min(x / i, n);

	return cnt >= k;
}

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

	cin >> n >> k;

	ull hi = 100000 * 100000;
	ull lo = 1;
	for (int it = 0; it < 100; ++it) {
		double mid = (hi + lo) / 2;

		if (decision(mid)) hi = mid;
		else lo = mid;
	}

	cout << hi;

	return 0;
}

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

typedef long long ll;

ll N;
ll k;

//x 앞에 숫자가 k개 이상 존재하는지 검사
int check(ll x) {
	ll cnt = 0;
	for (ll i = 1; i <= N; ++i)
		cnt += min(x / i, N);

	return cnt >= k;
}

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

	cin >> N;
	cin >> k;

	ll high = min((ll)10000000000, N*N);
	ll low = 1;
	while (low < high) {
		ll mid = (high + low) / 2;
		if (check(mid)) high = mid;
		else low = mid + 1;
	}
	cout << high;
	return 0;
}

틀린 풀이

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

typedef long long ll;

ll n, k;
//countPair[i]: (1,1) ~ (i, )까지 만들 수 있는 수의 개수
ll countPair[100001] = { 0 };

void getCountPair() {
	/*
	(1,1) ~ (i, )까지 만들 수 있는 수의 개수		-> countPair[i]
	= (1,1) ~ (i-1, )까지 만들 수 있는 수의 개수	-> countPair[i-1]
	+ (i,i)						-> 1 개
	+ i < j <= n일 때, (i,j)와 (j,i)			-> 2 * (n - i) 개
	*/

	countPair[0] = 0;
	for (int i = 1; i <= n; ++i)
		countPair[i] = countPair[i - 1] + 1 + 2 * (n - i);

	return;
}

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

	cin >> n >> k;
	getCountPair();

	// k번째로 큰 수를 구해라
	//-> k번째 수가 속한 (1,1) ~ (i, )중 가장 작은 i를 가진 범위를 찾는다 
	int i = 1;
	while (true) {
		if (k > countPair[i]) ++i;
		else break;
	}

	//(i-1, ) ~ (i, )까지 만들 수 있는 수 중 k번째 수를 찾는다
	ll kk = countPair[i - 1];
	if (++kk == k) {
		cout << i * i;
		return 0;
	}
	int j = i;
	while (kk < k) {
		j++;
		kk += 2;
	}

	cout << i * j;
	return 0;
}

• 반례

100000
1000000000
output : 352629984
answer : 204535821

• 틀린 이유:

📌참고자료

• 백준 1300 K번째 수 풀이
  https://kbw1101.tistory.com/29