====== 적당한 휴식은 필수 ======

===== 풀이 =====
  * 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 이 되도록 만드는 것은 간단하고 여러가지 방법이 있을것 같다. 내 경우에는 아래처럼 되도록 구성했다
    * <code>
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
   ...
</code>
   * N이 짝수인 경우에는 답을 2N으로 만들수 있는 구성 방법이 존재한다.
     * 내 경우에는 그냥 이것저것 시도해보다가 다음과 같은 방법을 찾아서 그렇게 AC를 받았다.
       * <code>
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
</code>
       * <code>
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
</code>
  * 하지만, 사실 풀기는 풀었지만, 다른 비슷한 문제를 풀때에도 도움이 되기 위해서는, n에 대한 답이 n-1에 대한 답을 확장하는 형태가 되도록 생각하는 연습을 하는 것이 좋다.
  * 그렇다면, 0..2N-5까지를 커버하는 (N-2)*(N-2) 그리드가 있다고 했을때, 행과 열을 2개씩 추가해서 이것들이 각각 2N-4, 2N-3, 2N-2, 2N-1 이 되도록 만드는 연습을 해보자
    * 다음처럼 추가하면 된다. 
      * <code>

2N-4 0..0  1
 0   XXXX  0  
...  XXXX ...
     XXXX  
 0   XXXX  0
 0   0..0 2N-2 
</code>
      * <code>
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 
</code>
  * 실제 코드는 이것을 살짝 바꿔서 구현했다.
  * 시간복잡도는 구성하는데에는 O(n)이지만, 출력량이 O(n^2) 이라서 O(n^2)


===== 코드 =====
<dkpr py>
"""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()

</dkpr>

{{tag>BOJ ps:problems:boj:골드_2}}