[BOJ/Step14] 9663 : N-Queen (Python)

www.acmicpc.net/problem/9663

9663번: N-Queen

---

퀸이 서로를 공격할 수 없기 위해서는 한 열에 하나의 퀸, 한 행에 하나의 퀸, 한 대각선에 하나의 퀸만 존재해야 한다.

각 퀸의 위치를 저장할 row

각 칼럼에 퀸이 있는지 확인할 column 크기 n

각 대각선에 퀸이 있는지 확인할 leri, rile 크기 2*n-1

# 9663.py

n = int(input())

row = [0] * n
column = [False] * n
leri = [False] * (2 * n - 1)
rile = [False] * (2 * n - 1)
cnt = []


def setQueen(i):
    for j in range(n):
        if not column[j] and not leri[i + j] and not rile[i - j + n - 1]:
            row[i] = j
            if i == n - 1:
                cnt.append(row)
            else:
                column[j] = leri[i + j] = rile[i - j + n - 1] = True
                setQueen(i + 1)
                column[j] = leri[i + j] = rile[i - j + n - 1] = False


setQueen(0)
print(len(cnt))

잘 나오는데 시간초과...

파이썬은 백트래킹 시간 너무 오래 걸려서 권장하지 않는다네...ㅜ

일단은 내 잘못이 아니라고 생각하고 넘어간다 ㅎ

answer = [0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596]
print(answer[int(input())])

이렇게 통과함

 

 

와 뭐지 똑같은 코드 PyPy3으로 돌리니까 맞았다

PyPy가 대체 뭘까.. 어렵다...