문제

https://www.acmicpc.net/problem/1846
장기의 말 중 차(車)를 게임판 위에 다음과 같은 규칙하에 배치하려고 한다.
1. N x N 크기의 게임판 위에 배치한다.
2. 서로 같은 세로/가로 줄에 두개의 차가 위치할 수 없다.
3. 두 대각선이 지나는 칸 위에는 차가 위치할 수 없다. 대각선은 아래 그림과 같다.

이 때, 조건을 만족하는 배치를 할 경우, 각 줄의 몇 번쨰 간에 배치했는지를 출력한다.

아이디어

핵심 아이디어

BOJ - 1846 ) 장기 링크의 풀이를 참고하였습니다.

1. 차의 배치는 규칙성을 갖고 있으며 N이 홀수/짝수 일때, 서로 다른 규칙성을 갖고 있다.
   ※ 규칙은 다양하게 찾을 수 있을 것 같습니다. 아래의 규칙은 제가 위의 풀이 링크를 보고 참고하여 찾은 규칙성입니다.

2. 짝수일때의 규칙성
   

• 0 행과 N 행은 공통적으로 가운데 열에 위치한다.
• 1 ~ N // 2 행은 대각선 영역의 왼쪽 열, N // 2 + 1 ~ N - 1 행 까지는 대각선 영역의 오른쪽 열에 위치한다.

3. 홀수일때의 규칙성
   

• 0 행은 가운데 열에 위치한다.
• N // 2 + 1 행은 가장 마지막열에 위치한다.
• 나머지 행은 대각선 영역의 왼쪽 열에 위치한다.

코드

N = int(input())
if N == 3:
    print(-1)
if N % 2 == 0: # 짝수
    print(N // 2)
    for i in range(1, N // 2):
        print(i)
    for i in range(N // 2, N - 1):
        print(i + 2)
    print(N // 2 + 1)
else:
    print(N // 2 + 1)
    for i in range(1, N // 2 + 1):
        print(i)
    print(N)
    for i in range(N // 2 + 2, N):
        print(i)

ETC

• N의 최대 크기가 10만이여서 백트래킹을 이용한 완전탐색은 시간초과가 나는듯 합니다. 일단 저는 시간초과 났습니다..