[PKU 3685. Matrix] 줄여서 생각해봅시다

우리가 문제에서 생각해야 하는 행렬의 최대 차수는 무려 5만차입니다

(여기서 말하는 차수는 행렬의 size를 의미합니다)

그리고 행렬 내의 i번째 행, j번째 열의 원소인 a_ij의 값은 i^2 + 100000*i + j^2 - 100000*j + i*j 이지요

(이하 a_ij는 (i, j)로 표기하겠습니다)

약간 고쳐서 간단히 만들면 (i+j)^2 - i*j + 100000*(i-j)가 됩니다

그런데 여태까지 ↘이 방향으로 오른쪽 위에서부터 왼쪽 아래까지 읽어내려오는 방식은

(즉, n차 행렬에 대해 (1, n), (1, n-1), (2, n), (1, n-2), (2, n-1), (3, n), (1, n-3), …, 이 순서로 읽어내려오는 )

행렬의 차원이 커지면 저 순서로 읽을 수 없게 되고 말아버립니다

그런데 최대 차수가 5만이니 차수를 하나하나 증가시키면서 검사하는 방법은 거의 불가능에 가깝다고 봅니다

그래서, 1/5000로 줄여서 최대 차수가 10차인 문제에 대해 생각해보도록 하겠습니다

단, 1/5000로 줄일 때

(i, j)의 값을 나타내는 식의 일부에 해당하는 '10만'에도 적용시켜서 (i, j) = (i+j)^2 - i*j + 20*(i-j)로 생각하도록 합니다

이렇게 계산해서 나타낸 10차 행렬은 다음과 같습니다

원소가 100개밖에 되지 않으니 다루기 훨씬 쉬워지긴 했지만

'원래 문제에서 발생하는 현상이 그대로' 위의 그림에도 존재합니다

이 행렬의 경우

'3차까지는' ↘이 방향으로 읽어내려오는 방식이 유효하지만 4차부터는 그렇지 않죠

게다가 차수가 더 커지면 각각의 행 안에서의 최소값이 오른쪽 끝에 있지 않습니다

붉은색으로 표시해둔 값이 각각 i번째 행 안에서의 최소값이 되는데, 이 최소값의 좌우로는 값이 커집니다

만약 이 행렬에 대해서 m번째로 작은 값을 '규칙적으로' 찾아낼 수 있다면

그것을 확장해서 원래 문제에 적용할 수 있지 않나 생각합니다만- 어떻게 생각하시는지?