일단 이 문제를 2분법으로 풀 수 있는 이유부터 말씀드릴게요.

f(x)를 A[i][j] <= x인 것의 갯수라고 합시다.

x<y라면 y = x+a (단 a>=1) 꼴로 나타낼 수 있습니다.

그러면 집합을 다음과 같이 둬 봅시다.

A = {(i,j)|A[i][j]<=x이고, 1<=i<=n and 1<=j<=n}

B = {(i,j)|x+1<=A[i][j]<=x+a이고, 1<=i<=n and 1<=j<=n}

C = {(i,j)|A[i][j]<=x+a이고, 1<=i<=n and 1<=j<=n}

여기서 A[i][j] = i*j이고 i*j는 정수 집합인 Z에 포함되고요. (심지어 자연수 집합 N에도 포함되죠)

그리고 잘 보시면 C이면서 A의 여집합은 B임을 알 수 있어요. 즉 n(A) + n(B) = n(C)인데 n(B)>=0이므로 n(A)<=n(C)입니다.

따라서 x가 증가할수록 f(x)가 단조 증가하기 때문에 이분 탐색 적용 가능합니다.

간단히 서술드리자면 다음과 같습니다.

이분 탐색의 원리는 자연수 x에 대해 어떤 조건 P(x)가 참이면 P(x+1)도 참이라는 것입니다. 우리의 문제는 P(x)가 참이 되는 최소의 x를 구하는 것인데, 적당히 큰 구간을 잡아 중점 m에 대해 P(m)을 보면

- P(m)이 참 : 답이 m 이하

- P(m)이 거짓 : 답이 m+1 이상

임을 이용해 초기 구간의 길이가 t이라고 하면 log t 정도번만 반복해 x를 찾을 수 있습니다.

이 문제에서 P(x)는 'N*N 배열에서 x 이하의 수가 k개 이상 있다'의 명제입니다. N*N 배열에 x 이하의 수가 몇 개 있는지 구하는 건 1에서 N^0.5까지 x/i를 더한 다음, 대칭을 이용해 구할 수 있습니다 (이 부분은 고민해보시길 바랍니다). 그럼 마찬가지로 탐색을 통해 x를 구할 수 있고, 그 x가 k번째 수가 됩니다.

결과적으로 이 두 아이디어를 종합하면 문제의 정해가 됩니다.

그러면 결정 함수를 어떻게 만드느냐.

f(x)를 A[i][j]<=x이고, 1<=i<=n and 1<=j<=n인 (i,j)의 갯수로 보자고 했는데. 이것은 사실

Row번째 행만 생각해 본다면

Row*j <= x인 것의 갯수를 구하는 건 쉽습니다. 그낭 x/Row거든요. 그런데 행에 대응되는 열이 최대 n개니까 min(x/Row,n)이 되겠죠..

그런데 우리는 1번째 행, 2번째 행, ... , n번째 행까지 모두 봐야 하기 때문에 결론적으로는 min(n,x) + min(n,x/2) + ... + min(n,x/n)이 될 거고요.

tt>0인 자연수 tt에 대해서

0<=a<b라면

[aa/tt] <= [bb/tt] 인 것도 자명한 소리죠?

지금 제 소스 보니까 어떻게 풀었는지 모르겠네요 ㅋㅋㅋㅋㅋㅋ ㄹㅇ..

어또케 풀었지??

K를 right에 넣어도 답이 나오는 이유는 https://www.acmicpc.net/board/... 입니다.

다들 멋진 증명 감사드립니다. 덕분에 해결했는데 한가지 머릿속으로 이해가 안되는게 있습니다.

제가 여기 있는 증명을 다 이해못해서 남은 궁금증인지 쓸데없는 고민인지 잘 모르겠습니다.

n = 3이라고 할 때,

{1,2,3},{2,4,6},{4,6,9}로 7이란 값은 나오지 않습니다.

어떻게 이분법으로 7이란 값을 피해서 계산 할 수 있는 건지 궁금합니다.

아니면 제가 아직 이분법이라는 알고리즘에 대해서 제대로 이해하지 못한것인지 ㅠㅠ

어떠한 수 x가 한 번 이상 나온 경우에.

x-1 이하의 수가 나온 횟수 < x 이하의 수가 나온 횟수입니다. a>0이라면, x<x+a라는 것을 생각해 보시면 됩니다.

만약에, 어떠한 수 x가 나오지 않았다면

x-1 이하의 수가 나온 횟수 = x 이하의 수가 나온 횟수일 거에요. 이건 당연한 건가요? (혹여나 그게 아니라 생각이 되시면 증명해 보시는 것도..)

그러면 어떠한 aa를 기준으로

aa-1 이하의 수가 나온 횟수가 tt이고, aa 이하의 수가 나온 횟수가 qq일 때

tt<m이고, qq>=m이라면, aa는 m번째 나온 수라는 걸 알 수 있어요.

그러면

1 2 3

2 4 6

3 6 9

를 볼까요?

1 이하의 수는 1개

2 이하의 수는 3개

3 이하의 수는 5개

4 이하의 수는 6개

6 이하의 수는 8개

7 이하의 수는 8개

8 이하의 수는 8개

9 이하의 수는 9개에요.

자 여기서 어떻게 8번째 수가 7,8이 아닌 6임을 알 수 있느냐면..

6을 보면, 6 이하의 수는 8개 이지만, 4 이하의 수는 6입니다. 그러한가요?

그런데 7을 보면, 7 이하의 수는 8개이지만, 6이하의 수 역시 8개입니다. 이 말인 즉슨, 7은 존재하지 않는다는 겁니다.

8을 봐도 마찬가지입니다. 8이하의 수는 8개이지만, 7이하의 수 역시 8개입니다. 이 말인 즉슨, 8 역시 존재하지 않는다는 겁니다.

어떠한 수 x가 존재하느냐. 존재하지 않느냐는.

어짜피 나오는 수가 정수 집합에 속하기 때문에

배열에서 나오는 x 이하의 수의 갯수 - 배열에서 나오는 (x-1) 이하의 수의 갯수가 0인지 아닌지만 보시면 됩니다.

저는 특정 조건을 만족할 때, 조건 하나를 더 따져주는 방식으로 좁혀나갔습니다.

위 질문의 요지는 "7이 배열에 있는지 없는지를 어떻게 아느냐"가 아니라 "어떻게 7이란 값을 답으로 내놓지 않을 수 있냐"인 것 같습니다.

P(x)는 'N*N 배열에서 x 이하의 수가 k개 이상 있다'의 명제입니다. 가령 k = 5라고 하면, x = 7일 때, x 이하의 수가 8개 이상 있으므로 P(7)은 참입니다. 하지만 x = 6, x = 5처럼 7보다 작은데도 참이 되는 x의 값이 있고, 우리가 원하는 것은 "P(x)가 참인 가장 작은 x"를 찾는 것이므로, P(7)이 참이라는 것을 알아내면 7보다 작은 범위에서 탐색을 계속해야 합니다. 즉 7을 피하는 것이 아니라, 7을 확인하더라도 그보다 작은 답이 있을 수 있으므로 7 아래로 내려가는 것입니다.

답변 많이 달아주셨는데 면접 준비하느라 이제 확인하였습니다. 너무 감사드립니다.

두분 다 증명으로 이 문제 완벽히 이해한거 같습니다..ㅠㅠ

다음번에는 이 부분 고려하면서 풀수 있을거 같아요!