1799

[백준 1799] 비숍 C++

1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 백트래킹 연습하기 #4 1. 문제풀이 아이디어 비숍의 특징 : 체스판의 검은 칸에 있는 비숍과 흰색 칸에 있는 비숍은 서로 아무 영향을 끼칠 수 없다. 이 문제를 정석적인 백트래킹으로 푼다면 시간 복잡도는 O(2^(N*N))이 된다.. 체스판에 모든 곳에 비숍을 놓을 수 있고 N=10이면 각각의 칸마다 ( 비숍을 놓는다 or 놓지않는다 ) 2가지의 경우가 생기므로 2^100가지의 경우를 모두 탐색해야한다 2^100 = 1.2676506e+30 이므로 참신한 방법이 필요하..