[Baekjoon/백준] 1300번: K번째 수(C/C++)

단계별로 풀어보기 21단계(이분 탐색) 6번 문제

https://www.acmicpc.net/step/29

이분 탐색 단계

---

백준 1300번: K번째 수

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

1300번: K번째 수

---

문제 설명

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.

배열 A와 B의 인덱스는 1부터 시작한다.

---

입력과 출력

입력: 첫째 줄에 배열의 크기 N이 주어진다. N은 10^5보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(10^9, N^2)보다 작거나 같은 자연수이다.

출력: B[k]를 출력한다.

---

접근 방법

이번 문제는 배열의 크기 N와 숫자 k를 입력받아 일차원 배열 B[k]를 출력하는 문제다.

간단히 생각하면 배열 A[N][N]와 B[N*N]에서 B[k]를 찾으면 되는데, 문제는 N 값 범위가 최대 10^5라서 N*N은 10^10이 되므로 시간 초과도 발생할 것이다. 또한 이중 배열 A[10^5][10^5]은 메모리 초과로 사용하기 쉽지 않다. 따라서 이분 탐색을 통해서 문제를 해결해야한다.

일단 우리는 배열의 k번째 값을 찾아야한다. 그러니까 어떠한 값이 k번째 인지 아닌지 판단할 수 있어야한다. k번째 값인지를 판단하려면 그 값보다 작거나 같은 숫자가 k개보다 작으면 안되면 된다. 그러니까 값이 배열의 k번째니까 최소 그 아래 값이 k개 이상은 있어야한다는 것이다. (그보다 작으면 k번째 숫자가 될 수 없으므로)

그리고 문제에서 A[i][j] = i * j 라고 했으므로, 배열에 있는 값들은 i의 배수가 된다. 따라서 k번째 값보다 작거나 같은 숫자 개수는 k번째 값 / i 한 값이 된다. 하지만 배열이 N*N이므로 나눴을 때 N보다 큰 경우는 나오면 안된다. 따라서 k번째 값 / i 와 N 중 최솟값들을 저장해 k보다 작은지 확인해 작다면 더 큰 값을, 크다면 더 작은 값을 탐색하면 문제를 해결할 수 있다.

이번 문제는 해결이 쉽지 않아서 블로그 글들을 참고해서 문제를 해결했다.

---

코드

#include <iostream>
using namespace std;

int min(int x, int y) {
	return x > y ? y : x;
}

int main(int argc, char *argv[]) {
	int N, k, start, end, mid, count, result = 0;
	cin >> N;
	cin >> k;

	start = 1;
	end = k;

	while (end >= start) {
		mid = (start + end) / 2;
		count = 0;
		for (int i = 1; i <= N; i++)
			count += min(mid / i, N);

		if (count < k)
			start = mid + 1;
		else {
			end = mid - 1;
			result = mid;
		}
	}

	cout << result << endl;

	return 0;
}

---

결과

백준 제출 결과