BOJ 34768 숫자 배치하기

각 $p$에 대해 직사각형에 최소한의 개수의 수를 넣는 방법을 고민해 보면 다음의 관찰을 할 수 있습니다.

• $\frac{N^2}{4}$를 초과하는 $p$에 대해서는 수를 하나만 끼워넣는 것은 불가능합니다. (범위 내의 수 중에서 $p$의 배수는 $p$로 유일하기 때문)
• 수를 두 개 끼워넣어서 조건을 충족하려면 $p-1$과 $p+1$을 끼워넣는 방법이 있습니다.

이를 최대한 활용하는 것을 시도해 보면 다음과 같은 모양이 나오게 됩니다.

이러한 2줄짜리 체인을 $N$줄의 행렬로 만드는 방법은 적어도 다음의 두 가지가 있습니다.

• $N$의 배수에서 줄바꿈을 하여 다음과 같이 배치합니다. 그러면 $N$의 배수인 $p$에 대해서는 직사각형 내의 수가 $p-1, p-2, \cdots, p-(N-1)$이 한 번씩, $p+1, p+2, \cdots, p+(N-1)$이 한 번씩 등장하게 되며, $p-i$와 $p+i$를 짝지어 각각 $p$의 배수가 되므로 조건을 충족합니다. 이러면 맨 왼쪽 위와 맨 오른쪽 아래에 빈 칸이 하나씩 남는데, 거기에 $\frac{N^2}{2}$를 배치해 주면 1 이상 $\frac{N^2}{2}$ 이하의 모든 정수의 합의 2배는 $\frac{N^2}{2}$의 배수이므로 역시 조건을 충족합니다.

• 줄 끝마다 $1 \times 4$의 직사각형 영역을 차지하면서 그 안에 $p-1$과 $p+1$이 오도록 지그재그로 다음과 같이 배치합니다. 그리고 마지막 남는 칸에 1을 배치하면, $\frac{N^2}{2}$가 이루는 정사각형 내에는 $\frac{N^2}{2} - 1$과 1이 오게 되어 모든 조건을 충족합니다. 단, $N = 4$일 경우 두 개의 1이 서로 붙어있으므로 예제 등을 이용하여 별도로 처리해야 합니다.