K번째 수

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

---

풀이

2차원 배열 A는 A[i][j] = i*j이고 배열 B는 2차원 배열 A의 요소를 1차원 배열의 오름차순으로 정렬한 것이다.
입력값 K가 6이라는 것은 B[6] = 4라는 의미이거나 B의 요소가 4일 경우 그와 작거나 같은 요소의 개수가 최소 6개라는 뜻이다.(왜냐하면 오름차순이기 때문)
즉, 원소 개수를 통해 이분 탐색을 진행하여 해결한다.
이때 원소의 최솟값은 1이고 원소의 최댓값은 min(10^9, N^2)으로 조건으로 되어있다.

요소의 값에 따라 원소 개수를 구하는 함수는 몇 가지 아이디어를 통해 구현한다.
1. 배열 A를 보면 구구단으로 볼 수 있다. 1행은 1단, 2행은 2단, i행은 i단이라는 것을 알 수 있다.
2. 자연수 m보다 작은 i단의 개수는 m / i의 몫이다. 예를 들어, 6보다 작은 1단의 개수는 6 / 1 = 6이고 2단의 개수는 6 / 2 = 3이다.
(이때 중요한 점은 열의 크기이다. N이 3일 경우 6 / 1 = 6이지만 열의 크기가 3이므로 3으로 보정되어야 한다.)