Nostalgia

어떤 배치에서 $X=M$을 만들 수 있다면 행렬을 전치하여 $X=-M$도 만들 수 있다. 따라서 $X\geq0$만 생각하면 된다.

열 최댓값의 합을 최대화하면 $N^2-N+1,\cdots,N^2$를 각 열의 최댓값으로 둘 수 있다. 한편 행 최댓값을 오름차순으로 $M_1<\cdots<M_N$이라 하면 앞의 $i$개 행에 $Ni$개의 원소가 들어가므로 $M_i\geq Ni$이다. 이로부터 가능한 절댓값의 최댓값은

$$L=\frac{N(N-1)^2}{2}$$

임을 얻고, 실제로 행 우선으로 $1,2,\cdots,N^2$를 배치하면 $X=L$을 달성한다.

$0\leq X\leq (N-1)^2$에서는 큰 수 $N^2-N+1,\cdots,N^2$를 대각선에 둔 $X=0$ 구성에서 첫 행의 최댓값만 $N^2-N+1-X$로 낮추고, 빠진 큰 수를 첫 열의 다른 위치로 옮기면 정확히 $X$를 만들 수 있다.

그보다 큰 $X$에서는 최대 구성에서 시작한다. 마지막 행의 큰 수들은 그대로 두어 열 최댓값의 합을 고정하고, 앞 $N-1$개 행의 최댓값을 뒤쪽 행부터 가능한 만큼 하나씩 키워 $L-X$만큼 행 최댓값 합을 증가시킨다. 각 목표 행 최댓값 $M_i$는 $M_i\geq Ni$와 엄격한 증가 조건을 만족하며, 남은 작은 수를 각 행에 채워 실제 배치를 만들 수 있다.

음수 $X$는 완성된 행렬을 전치한다. 구성 자체는 $O(N^2)$에 가능하다. Solution written by GPT5.6