ababc1005   2년 전

첫 AC에서 400ms가 나와서 나름 줄인다고 48ms까지 줄였는데 

정답자 리스트를 보면 0ms로 푸신 분들도 많더라구요.

제 생각에는 백트래킹을 하면서 이전 상태 저장하고 다시 되돌리는 과정이 오래걸리지 않나.. 하는 생각이 드는데

그게 주범이 맞을까요?

해결법으로는 column + row 말고 column - row도 boolean array로 관리해서 영역을 한방에 on-off 시켜주는 거긴 한데

그래봐야 max 1/N배로 연산이 줄어드는거라 뭔가 놓치고 있는 게 있을까 싶습니다.

항상 백트래킹 할 때마다 시간이 평균보다 많이 나오는 편이라서  

또 다른 원인은 없을까 이참에 확실히 공부해두고 싶네요!

flappybird   2년 전

아직 안 풀어봤는데 아마 왼쪽위와 오른쪽아래로향하는 방향의 대각선과 오른쪽위에서 왼쪽아래로 가는 대각선의 교점에 비숍이 놓이는 형태이니 체스판 크기가 N이라하면 2N-1개의 대각선과 그 반대방향대각선을 정점으로해서 이분매칭하는 방법으로 풀었을거같네요


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