N=3일때 A[i][j]는 위처럼 생겼고, B를 구해서 정렬해보면 B = {1, 2, 2, 3, 3, 4, 6, 6, 9} 이렇게 된다.
1base index로 K(=7)번째 숫자를 구해보면 6이 된다.
임의의 숫자(=m)를 찍어서 그 숫자보다 작거나 같은 원소의 수를 계산하는 로직을 생각해보자. (이게 되면 이진탐색이 가능해지므로)
예를들어 임의의숫자 m=4로 가정하고 생각해보면,
위 3x3 행렬에서
1행에는 4보다 작거나 같은 원소가 3(=N)개가 있다.
2행에는 4보다 작거나 같은 원소가 2개 있는데, 2행은 모두 2의 배수이므로 4(=m)/2(=행=i)로 계산할 수 있다.
3행에는 4보다 작거나 같은 원소가 1개 있는데, 3행은 모두 3의 배수이므로 4/3=1로 계산할 수 있다.
1,2,3행의 숫자를 모두 더해보면 3+2+1=6이 되는데, 이게 바로 임의로 골랐던 숫자 4(=m)보다 작거나 같은 원소의 갯수이다.
즉 4를 찍었더니 우리가 원했던 7번째 숫자가 아니라 6번째 숫자였다고 하는 결과가 나왔다는 것이다.
이런 느낌으로 임의로 찍은숫자를 키워가면서 이진탐색을 해볼 수 있다는 감이 올 것이다.
위의 1,2,3행 로직을 따져보면 min(N, m/i)로 행마다 m보다 작거나 작은 원소의 수를 계산할 수 있음을 유추할 수 있고
int cnt=0;for(int i=1;i<=N;i++) cnt+=min(N, m/i);
위 로직으로 임의로 찍은 m에 대해서 몇번째 숫자인지 구할 수 있게 된다. (중복원소 포함이므로 upper_bound쪽으로 나옴)
위 아이디어만 이해하면 나머지는 비교적 트리비얼 하다.