[알고리즘/문제풀이][BOJ 1300번] K번째 수

K번째 수 문제는 최적화 문제를 결정 문제로 바꾸어 푸는 유형의 문제로 볼 수 있습니다. K번째 수를 X로 가정하면 X보다 작거나 같은 수는 K개 이상이라는 사실을 알 수 있습니다. 그보다 작으면 K번째 수가 될 수 없기 때문입니다. 

작거나 같은 수가 K개 이상인 수 중 가장 작은 값을 찾는 문제로 생각해볼 수 있습니다. 이와 같은 최적화 문제를 X이상의 수에 대해 자기 자신보다 작거나 같은 수를 K개이상 가지고 있는지 확인하는 결정문제로 바꿀 수 있습니다.

이러한 결정문제는 이분법을 이용하여 해결할 수 있습니다.

작성한 코드는 다음과 같습니다.

#include<stdio.h>
#pragma warning(disable : 4996)
//https//ark-hive.tistory.com
int N, K;

int min(int a, int b) {
	if (a > b) return b;
	else return a;
}

int function(int num) {
	int sum = 0;

	for (int i = 1; i <= min(num, N); i++) {
		if (min(num / i,N) > 0) {
			sum += min(num/i, N);
		}
	}

	return sum;
}

int main(void) {
	scanf("%d %d", &N, &K);

	int ans = 0;
	int lo = 0, hi = K;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		if (function(mid) < K) {
			lo = mid + 1;
		}
		else {
			ans = mid;
			hi = mid - 1;
		}
	}

	printf("%d\n", ans);
}

문제는 다음의 링크에서 확인할 수 있습니다.

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