어떤 문제인가?

$N\times N$ 타일에 $N$개의 퀸이 서로 공격하지 못하도록 두는 문제.

족보

N-Queen 수열이라는 게 있다. 다음을 참고하자.
-> https://oeis.org/A002562

최적화 가능한 부분

1. 열 또는 행 단위로 확장해나가기
   기준을 잡고 배치하면 배치한 열 또는 행 이전은 보지 않아도 된다. 그러니까, 예를 들어 행 단위로 확장한다면 3행에 배치할 시 1,2행은 볼 필요가 없다.
2. 타일 상태를 저장하지 말고 퀸의 위치를 저장
   타일 상태를 저장하는 방식으로 하면 $N$이 커질수록 퀸 위치를 비교하는 것보다 시간이 더 걸리게 된다. 퀸 위치를 대신 저장하자. 그리고 그게 공간복잡도도 더 적다.

내 코드

#include <stdio.h>
#include <stdlib.h>

int N,Q=0;
int X[15]={0},Y[15]={0};

int c(int i, int l) {
   int j=0;
   for(;j<l;j++) {
       if(i==Y[j]||abs(X[j]-l)-abs(Y[j]-i)==0)
          return 0;
   }
   return 1;
}

void d(int l) {
   int i;
   if(l==N) {
       Q++;
       return;
   }
   for(i=0;i<N;i++) {
       if(c(i,l)) {
           X[l]=l;
           Y[l]=i;
           d(l+1);
       }
   }
}

int main() {
   scanf("%d",&N);
   d(0);
   printf("%d",Q);
}

내 폰(Galaxy A7)에서 돌렸더니 $N=14$일 때 1분이 넘게 걸리길래 시간초과 뜨면 어떡하지 생각했는데, 백준에서는 5초 좀 못되는 시간이 걸렸다. 역시 갓백준;

남들의 풀이

위에서 말했듯 이 문제의 $N=1$ 부터 $N=14$까지 답은 이미 널리 알려진 상태라, 아예 대놓고 배열에 모든 값을 담고 $N$번째 값을 보여주는 답안이 있지 않을까 생각했다.

그리고 내 예상은 빗나가지 않았다.

a[]={0,1,0,0,2,10,4,40,92,352,724,2680,'7x',73712,365596};main(){printf("%d",a[atoi(gets(a))]);}

cgiosy님의 소스
-> https://www.acmicpc.net/source/6977688

다들 한번 정도는 정공법으로 푸셨으니 이렇게 하시는 것이라 생각한다. 답이 이미 공개되었고, 숏코딩에 가장 적합한 먹잇감이니까 그럴 수도 있겠다.