이동식 저장소

오랜만에 문제를 하나 풀어보자.

주어진 규칙으로 채워지는 격자의 일부분을 출력하는 문제이다.

격자의 크기가 $10,000\times 10,000$이므로 격자를 미리 채우는 방법은 시간도 오래 걸리고, 문제의 의도에도 맞지 않다. 이 문제의 의도는 격자에 쓰인 수를 좌표만 가지고 구하는 것이다.

격자를 관찰해 보면, 중심이 같은 정사각형으로 이루어져 있다는 사실을 알 수 있다.

임의의 점 $(r,c)$과 $(0,0)$ 사이의 유클리드 거리는 $max(|r|,|c|)$이다. 이 값을 $d$라고 하고, $(r,c)$가 속한 정사각형의 지름이라고 부르자. 수학적으로는 존재하지 않는 말이지만, 이 문제를 풀 때만 사용하겠다.

지름이 $d$인 정사각형에는 다음 범위의 수가 적혀 있다.

• $d=0:[1,1]$
• $d=1:[2,9]$
• $d=2:[10,25]$
• $d=3:[26,49]$
• $⋮$
• $d=d_0:[(2d_0-1{)}^2+1,(2d_0+1{)}^2]$

따라서 $d$를 알면 해당 좌표에 적힌 수의 범위를 알 수 있다. 이제 수를 정확히 계산하는 방법을 생각해 보자.

각 정사각형에서 제일 작은 수가 적혀 있는 좌표를 정사각형의 시작점이라고 하자. $d>0$일 때 정사각형의 시작점은 다음과 같다.

순서대로 나열하면 $(0,1),(1,2),(2,3),\cdots$이다. 즉 $d=d_0$인 정사각형의 시작점은 $(d_0-1,d_0)$이고, 여기에는 $(2n-1{)}^2+1=4n^2-4n+2$가 쓰여 있다. 이제 정사각형을 다음과 같이 네 부분으로 나눌 수 있다.

점 $(r,c)$가 각 타입에 속하는 조건은 다음과 같다.

$$\{\begin{array}{ll}r=d_0,c>-d_0& (type=3)\\ c=-d_0,r>-d_0& (type=2)& \\ r=-d_0,c<d_0& (type=1)\\ c=d_0,r<d_0& (type=0)\end{array}$$

$type$별 시작점(위 그림에서 동그라미로 표시한 좌표)에 쓰인 수 $b$는 다음과 같다.

$$b=\{\begin{array}{ll}4n^2+2n+2& (type=3)\\ 4n^2+2& (type=2)& \\ 4n^2-2n+2& (type=1)\\ 4n^2-4n+2& (type=0)\end{array}=4n^2-4n+2+(2n\times type)$$

$type$별 시작점과 $(r,c)$ 사이의 거리 $res$는 다음과 같다.

$$res=\{\begin{array}{ll}c+(d_0-1)& (type=3)\\ r+(d_0-1)& (type=2)& \\ -c+(d_0-1)& (type=1)\\ -r+(d_0-1)& (type=0)\end{array}$$

따라서 $(r,c)$에 적혀있는 수 $N=b+res$이다. 이제 각 점에 대해 $N$을 구하면 된다. 단, $(r,c)=(0,0)$일 때 $N=1$이다.

한 가지 주의할 점은, 출력 형식에서 수의 자릿수를 맞추고 있다는 것이다. 자릿수가 작은 수는 앞에 공백을 추가로 출력해야 한다. 언어별로 적절히 처리하면 되겠다.