1300번 K번째 수

문제링크 : www.acmicpc.net/problem/1300

1300번: K번째 수

---

---

<알고리즘>

1) 범위를 [1,K]로 지정하고 그 범위의 중앙값인 mid보다 작은 숫자의 개수(cnt)를 파악합니다.

  1-1) cnt 파악방법

        i*j<=mid 가 가장 손쉽게 셀수 있는 방법이지만 이 방법은 같은 숫자 중복에 대응하기 어렵습니다.

        따라서, 좀 더 손쉽게 보기 위해 j<=mid/i 즉, mid값을 행으로 나누어 범위안에 들어오는 수를 찾습니다.

        그러한 방법으로 변환하면 cnt = min(N, mid/i)(1<=i<=N) 이 됩니다.

        N값과 비교하는 이유는 몫이 주어진 범위보다 큰 경우를 배제하기 위해서 입니다.

2) cnt와 K를 비교하여 범위를 조정합니다.

   2-1) cnt>=K 일경우, [1,mid-1]로 범위를 변경합니다.

   2-2) cnt<K일 경우 [mid+1,K]로 범위를 변경합니다.

3) 범위의 좌측값이 우측값보다 작은 동안 2번을 반복합니다.

 

 

 

범위를 K로 지정하는 이유 : 모든 K에 대해 K번째로 작은 수가 K이하이기 때문에

+) 참고 www.acmicpc.net/board/view/37110

글 읽기 - 소스코드 및 해설을 봐도 잘 모르겠습니다.

+) 참고 : www.acmicpc.net/board/view/31679#comment-57064

글 읽기 - 이분탐색으로 풀었지만 최대수와 if문에서 의문점이 남습니다.

 

 

 

 

메모리 : 2016KB    시간 : 32ms

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

//파라미터의 수보다 작은 수의 개수 return
int cntSmaller(long long N, long long m) {
	int total = 0;
	for (int i = 1; i <= N; i++) {
		total += min(N, m / i);
	}
	return total;
}
int main() {
	long long  N = 0;
	long long K = 0;
	cin >> N >> K;

	long long left = 1;
	long long right = K;
	long long middle = 0;
	long long result = 0;
	int cnt = 0;
	while (left <= right) {
		middle = (left + right) / 2;
		cnt = cntSmaller(N, middle);
		 if (cnt >= K) {
			right = middle - 1;
			result = middle;
		}
		else{
			left = middle + 1;
		}
	}

	cout << result;
	return 0;
}

 

 

+) 문제 그대로 코딩 했을 경우 => 메모리 초과

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

int main() {
	int N = 0;
	int K = 0;
	cin >> N >> K;

	vector<long long> number;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			number.push_back(i*j);
		}
	}
	sort(number.begin(), number.end());

	cout << number[K];

	return 0;
}