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

문제

[C++] 백준 1300: K번째 수 GOLD 1
https://www.acmicpc.net/problem/1300

 

---

 

접근 방법

이 문제는 N×N 곱셈표에서 오름차순으로 정렬했을 때 K번째에 오는 수를 구하는 문제다.
곱셈표 B를 아래와 같이 두고,

B[i][j] = i * j (1 ≤ i, j ≤ N)

이걸 평탄화해서 정렬했을 때 K번째 수를 찾는 게 목표다.

 

처음에는 실제로 N×N 배열에 값을 모두 채운 뒤 정렬해서 K번째 값을 찾는 방식으로 시도했는데,
N의 범위가 크다 보니 메모리 초과가 계속 발생했다..

그래서 곱셈표 전체를 만들지 않고, “어떤 값 X보다 작거나 같은 수가 곱셈표 안에 몇 개 있는지” 를 이용해서
이분 탐색(Parametric Search) 으로 답을 찾는 방식으로 바꾸었다.

 

이 알고리즘을 떠올리는 게 꽤 어려웠고, “실제 배열 없이 K번째 원소를 찾는 방법”을 이해하는 데 시간이 많이 걸렸던 문제였다.

 

상세 아이디어

1) 곱셈표를 직접 만들지 않고 생각하기

B[i][j] = i * j인 곱셈표를 직접 만들지 말고,

어떤 수 X가 주어졌을 때 “곱셈표 안에 X 이하인 수가 몇 개 있는지”를 세는 함수를 생각해보자.

 

예를 들어 i번째 행을 보면:

• i행에는 i, 2i, 3i, ..., Ni 까지가 있다.
• 이 중에서 X 이하인 값의 개수는
  X / i (단, 최대 N개를 넘을 수 없음)

→ 즉, i번째 행에서 X 이하인 값의 개수는: min(X / i, N)

이걸 1행부터 N행까지 다 더하면, “곱셈표 전체에서 X 이하인 값의 개수”가 된다.

 

2) “X 이하의 수가 K개 이상인가?”로 이분 탐색

우리가 구하고 싶은 건 “정렬했을 때 K번째 수”다.
이걸 다음처럼 바꿔서 생각할 수 있다.

“값이 X일 때, 곱셈표 안에 X 이하의 수가 K개 이상인지 확인할 수 있다면,
X를 이분 탐색으로 줄여 나가면서 K번째 수를 찾을 수 있다.”

 

그래서:

• 탐색할 값의 범위를 1 ~ k(k번째 수는 k를 넘지 않기 때문에)로 잡고
• 중간 값 mid에 대해 cnt = (mid 이하인 수의 개수) 를 구한 뒤:
  • cnt < K 이면 → 아직 K번째 수에 못 미쳤으므로 더 큰 값을 봐야 한다 → start = mid + 1
  • cnt >= K 이면 → K번째 수가 mid 이하에 존재할 수 있으므로
    일단 ret = mid로 저장하고, 더 작은 값이 가능한지 확인하기 위해 end = mid - 1로 줄인다.

이걸 반복하면 최종적으로 ret가 곱셈표에서 K번째 수가 된다.

 

구현 시 주의할 점

• cnt를 구할 때 mid / i가 N보다 커지는 경우가 있기 때문에
  반드시 min(mid / i, N)으로 잘라줘야 한다.
• 이분 탐색 종료 후에는 ret에 K번째 수의 후보 중 가장 작은 값이 남으므로, 그대로 출력하면 된다.

 

---

 

코드

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

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

	long long n = 0, k = 0;
	cin >> n >> k;

	long long ret = 0, start = 1, end = k;
	while (start <= end)
	{
		long long mid = (start + end) / 2;

		long long cnt = 0;
		for (int i = 1; i <= n; i++)
		{
			cnt += min(mid / i, n);
		}
		if (cnt < k)
			start = mid + 1;
		else
		{
			ret = mid;
			end = mid - 1;
		}
	}
	cout << ret;

	return 0;
}