N Queen

https://www.acmicpc.net/problem/3344

https://web.archive.org/web/20161108102345/http://penguin.ewu.edu/~trolfe/QueenLasVegas/Hoffman.pdf

• 보드판 크기를 N이라 두자.
• N을 6으로 나눈 나머지가 2 또는 3이 아니라면, 1부터 N까지의 수를 (짝수 오름차순) + (홀수 오름차순)으로 나열하도록 배치하면 된다.
• N을 6으로 나눈 나머지가 2이라면, 앞선 홀수 오름차순 리스트에서 1과 3의 위치를 바꾸고 5를 맨 뒤로 보낸다.
  • 즉 (짝수 오름차순), (3, 1, 7, 9, …, 5) 꼴이 될 것이다.
• N을 6으로 나눈 나머지가 3이라면, 2를 짝수 오름차순 리스트의 맨 끝으로 보내고 1, 3을 홀수 오름차순 리스트의 맨 뒤로 보낸다.
  • 즉 (4, 6, 8, …, 2), (5, 7, 9, … , 1, 3) 꼴이 될 것이다.
• 이런 식으로 모든 N >= 4 에 대한 해 중 하나를 구할 수 있다.

#include <iostream>
using namespace std;

int main() {
    int n;
    bool flag=0;
    cin>>n;
    if (n%2) flag=1;
    if ((!flag&&n%6!=2) || (flag&&(n-1)%6!=2)) {
        if (flag) n--;
        for (int i=1;i<=n/2;i++) cout<<2*i<<"\n";
        for (int i=1;i<=n/2;i++) cout<<2*i-1<<"\n";
        if (flag) cout<<n+1<<"\n";
    } else if ((!flag&&n/6!=0) || (flag&&(n-1)/6!= 2)) {
        if (flag) n--;
        for (int i=1;i<=n/2;i++) cout<<1+(2*i+n/2-3)%n<<"\n";
        for (int i=n/2;i>0;i--) cout<<n-(2*i+n/2-3)%n<<"\n";
        if (flag) cout<<n+1<<"\n";
    }
    return 0;
}