-
[PS] 백준 9663번: N-Queen문제해결 2023. 10. 25. 17:26
삼성 코테가 끝났으니 구현 말고 다른 유형도 풀어보고자
솔브닥 Class 4부터 뽀개보기로 했다.
이름이 행렬 제곱인 문제가 있길래 이 문제부터 해볼까 하다가,
살짝 감이 안잡혀서 일단 목록중에 보이던 N-Queen부터 처리했다...
내일은 저거 해버려야지...근데 이게 시간이 1.8초밖에 안걸린다니 서버가 얼마나 좋은걸까?
#include <bits/stdc++.h> using namespace std; #define pii pair<int, int> #define endl "\n" #define FOR(i, N) for (int i = 0; i < int(N); i++) #define FORL(e, S) for (auto& e : S) #define iib(r, c) (0 <= r && r < N && 0 <= c && c < N) int N, ans = 0; void back_track(int r, int c, int nqueen, int carr[15], bool to_bot[29], bool to_top[29]) { if (r >= N) return; if (nqueen >= N) { ans += 1; return; } int nr = r + 1; FOR(i, N) { if (carr[i] == -1 && !to_bot[nr - i + N - 1] && !to_top[nr + i]) { carr[i] = nr; to_bot[nr - i + N - 1] = true; to_top[nr + i] = true; back_track(nr, i, nqueen + 1, carr, to_bot, to_top); carr[i] = -1; to_bot[nr - i + N - 1] = false; to_top[nr + i] = false; } } } int main() { cin >> N; int carr[15]; memset(carr, -1, sizeof(int) * 15); bool to_bot[29]; memset(to_bot, false, sizeof(bool) * 29); bool to_top[29]; memset(to_top, false, sizeof(bool) * 29); FOR(i, N) { carr[i] = 0; to_bot[0 - i + N - 1] = true; to_top[0 + i] = true; back_track(0, i, 1, carr, to_bot, to_top); carr[i] = -1; to_bot[0 - i + N - 1] = false; to_top[0 + i] = false; } cout << ans << endl; return 0; }
'문제해결' 카테고리의 다른 글
[PS] 백준 25947번: 선물할인 (0) 2023.10.25 [PS] 백준 10830번: 행렬 제곱 (0) 2023.10.25 [PS] 코드트리: 왕실의 기사 대결 (0) 2023.10.25 [PS] 코드트리: 싸움땅 (0) 2023.10.25 [PS] 코드트리: 코드트리 빵 (0) 2023.10.25