백준 1300번: K번째 수

[문제 링크]

1300번: K번째 수

---

https://jaimemin.tistory.com/988 꾸준함 님의 블로그를 참고해서 겨우 이해한 문제였다. 아직도 조금 헷갈리긴 한다.

 

arr[i][j] 에 해당하는 숫자는 i * j 이므로, i행은 i의 배수로 이루어져 있다. (ex. i * 1, i * 2, i * 3 .... i * N)

이를 바탕으로 어떤 임의의 숫자 M을 i가 1부터 N까지인 경우에 대해 M / i 한 몫을 cnt 변수에 누적시키면 M은 cnt+1 번째 수라는 사실을 알 수 있다.

이 때 주의해야 할 것이 만약 M / i 한 몫이 N보다 클 경우 배열의 최대 범위보다 큰 값을 누적하게 되므로 오답이 출력되기 때문에 M / i 한 몫을 누적하는 것이 아닌 배열의 최대 길이인 N을 누적시킨다.

 

전부 누적시켰다면 입력받은 K와 비교를 하여 만약 cnt가 K보다 작을 경우 더 큰 mid값을 탐색하기 위해 start = mid + 1 로 바꿔준다.

반대로 cnt가 K보다 크거나 같을 경우 result에 mid 값을 저장하고, 최적의 해를 찾기 위해 end = mid - 1 로 바꿔서 재탐색한다.

 

start가 end보다 커질 때까지 위 과정을 반복하면 result에는 N X N 배열에서 K번째 수에 해당하는 정수가 저장되게 된다.

---

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

int main(void)
{
	int N, K;
	cin >> N >> K;

	int start = 1, end = K, result;
	while (start <= end)
	{
		int mid = (start + end) / 2, cnt = 0;
		for (int i = 1; i <= N; i++)
			cnt += min(mid / i, N);
		if (cnt >= K)
		{
			result = mid;
			end = mid - 1;
		}
		else
			start = mid + 1;
	}
	cout << result;

	return 0;
}

알고리즘 200일 프로젝트 - 47 day