dannyu_ndos   1년 전

명령형, 절차형으로 코드를 짜려니까 머릿속이 너무 복잡해져서, 함수형으로 짰거든요...;; 답은 다 맞는 것 같은데, 시간이 초과됩니다.

jtw7913   1년 전


질문 주신 코드가 TLE가 나는 이유는 탐색 방식이 비효율적이기 때문입니다.

현재 코드는

  • cells에 모든 좌표(n^2)를 넣고,

  • 각 칸마다 "퀸을 두거나 / 두지 않거나" 두 가지 분기로 탐색합니다.

즉, 경우의 수가 대략 2^(n^2)에 가까워져서, n이 조금만 커져도 절대 시간 내에 풀리지 않습니다.

힌트를 드리자면,

  1. 체스판의 각 행에는 퀸을 최대 하나만 둘 수 있으므로, 굳이 전체 칸을 탐색할 필요가 없습니다.

  2. row=0부터 row=n-1까지 내려가면서, 해당 행에서 놓을 수 있는 열을 선택하는 방식으로 탐색을 줄입니다.

댓글을 작성하려면 로그인해야 합니다.