jessestarr   10달 전

저는 (M-1)(N-1)개의 체스판에서 8x8개의 체스의 색을 조사하는 방식으로 했는데 FOR루프가 4개나 나오더라고요.ㅠㅠ

혹시 다르게 푸신분들은 어떻게 푸셨는지 궁금합니다.

leejk9592   2달 전

SAT(Summed Area Table)로 빠른 시간 내에 풀이가 가능합니다.

SAT는 인터넷 검색으로 무엇인지 쉽게 아실 수 있을 것이고,

row ^ col ^ (C[row][col] == 'B' ? 1 : 0) 값으로 2중 for문으로 int SAT[51][51]을 구성한 후,

tmp = SAT[8][8] - SAT[8][0] - SAT[0][8] + SAT[0][0] 부터 SAT[N][M] - SAT[N][M-8] - SAT[N-8][M] + SAT[N-8][M-8] 까지

2중 for문으로 각각 구할 때, for문 안에

if(tmp > 64 - tmp) // 체스판 색 반전한 것이 더 적게 칠해도 됨을 의미

then tmp = 64-tmp 

if(ret > tmp)

then ret = tmp

위 방식이 제가 생각하기엔 생각해 내기도 편하고, 답도 빨리[O(N^2)] 나올 거라 생각합니다.


P.S 오타가 있어서 2번 댓글삭제하고 재작성 했습니다

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