적당한 휴식은 필수

• N*N 격자라면 행과 열의 개수의 합은 2N이므로 만들수 있는 답의 상한은 2N이다.
• 그렇지만, N이 홀수일때를 생각해보면 답이 2N이 되는것이 불가능한것을 보일수 있다.
  • mex가 2N이 된다는 것은, R_i와 C_i들이 0..2N-1 이 된다는 말이므로, 전체의 합은 sum(R_i) + sum(C_i) = N*(2N-1) 인데 이 값은 홀수이다. 그런데 sum(R_i) = sum(C_i) 이므로, 치환하면 2*sum(R_i) = {홀수} 인데 이것은 불가능하다.
• mex가 2N-1 이 되도록 만드는 것은 간단하고 여러가지 방법이 있을것 같다. 내 경우에는 아래처럼 되도록 구성했다

  • 0 0 0 0 0
    1 1 0 0 0
    0 2 2 0 0 ...
    0 0 3 3 0
    0 0 0 4 4
       ...

• N이 짝수인 경우에는 답을 2N으로 만들수 있는 구성 방법이 존재한다.
  • 내 경우에는 그냥 이것저것 시도해보다가 다음과 같은 방법을 찾아서 그렇게 AC를 받았다.

    • 0 0 0                 0 0 0
      0 1 0     ...         0 0 0
      0 0 2                 0 0 0
        .                       .       
        .                       . 
        .                       .
      0    0   N/2     3N/2-3   0      0
      0   N/2   0.  ...  0   3N/2-2   0
      N/2  0    0        0     0    3N/2x-1

    • N=6 이라면 이렇게 된다
      
      0 0 0 0 0 0
      0 1 0 0 0 0    
      0 0 2 0 0 0     
      0 0 3 6 0 0
      0 3 0 0 7 0
      3 0 0 0 0 8

• 하지만, 사실 풀기는 풀었지만, 다른 비슷한 문제를 풀때에도 도움이 되기 위해서는, n에 대한 답이 n-1에 대한 답을 확장하는 형태가 되도록 생각하는 연습을 하는 것이 좋다.
• 그렇다면, 0..2N-5까지를 커버하는 (N-2)*(N-2) 그리드가 있다고 했을때, 행과 열을 2개씩 추가해서 이것들이 각각 2N-4, 2N-3, 2N-2, 2N-1 이 되도록 만드는 연습을 해보자
  • 다음처럼 추가하면 된다.

    • 2N-4 0..0  1
       0   XXXX  0  
      ...  XXXX ...
           XXXX  
       0   XXXX  0
       0   0..0 2N-2 

    • N=6 이라면 이렇게 된다 
      
      8 0 0 0 0 1
      0 4 0 0 1 0
      0 0 0 1 0 0
      0 0 0 2 0 0
      0 0 0 0 6 0 
      0 0 0 0 0 10 

• 실제 코드는 이것을 살짝 바꿔서 구현했다.
• 시간복잡도는 구성하는데에는 O(n)이지만, 출력량이 O(n^2) 이라서 O(n^2)

"""Solution code for "BOJ 33274. 적당한 휴식은 필수".

- Problem link: https://www.acmicpc.net/problem/33274
- Solution link: http://www.teferi.net/ps/problems/boj/33274

Tags: [ad hoc]
"""


def main():
    N = int(input())

    answer = [['0'] * N for _ in range(N)]
    if N % 2 == 0:
        for i in range(N // 2):
            answer[i][i] = str(i * 4)
            answer[-i - 1][-i - 1] = str(i * 4 + 2)
            answer[-i - 1][i] = '1'
    else:
        for i in range(1, N):
            answer[i][i] = answer[i - 1][i] = str(i)

    for row in answer:
        print(' '.join(row))


if __name__ == '__main__':
    main()