[PS]백준 N-Queen 문제 풀이모음

1. dp를 1차원배열 1개로 풀이 4352ms

queen의 위치를 저장한 배열 1개로 중복 열, 중복 대각선을 수식으로 계산하여 skip

현재까지 구한 queen 위치를 일일이 비교하므로 모든 경우의 수에서 최대 16번의 비교가 추가로 필요

https://chanhuiseok.github.io/posts/baek-1/

 

 

2. dp를 1차월배열 3개로 풀이 1652ms

현재까지 놓인 열번호, 우상대각선, 좌상대각선 관리 배열로 관리

현재 놓으려는 열 번호를 해시값으로 하여 배열에 접근하여 중복된 값이 있는지 확인하기 때문에 1번 풀이에서 현재까지의 queen 위치를 비교하는 방식보다 메모리는 더 쓰지만 속도는 빨라짐

https://3dpit.tistory.com/2