[B] Help General

n <= m 이라고 가정하자. 일반성을 잃지 않는다. 1) n == 1 모든 칸에 전부 놓을 수 있다. 답은 m 2) n == 2 손으로 그려서 잘 따져보면 oo..oo..oo..o oo..oo..oo..o 이런식으로 채워나가는 것이 최대임을 알 수 있다. 3) (n, m) != (3, 3), (3, 5), (3, 6), (4, 4) 여기에 속하는 격자판은 격자의 모든 칸에서 길이 n*m의 나이트 투어가 존재함이 알려져 있다. 따라서 우선 답은 n*m - n*m/2 를 넘을 수 없다. 그리고 격자판을 체스보드로 생각했을 때, 검은색 혹은 흰색에만 말을 놓으면 n*m - n*m/2 개를 놓는 답을 찾을 수 있다. 4) (n, m) == (3, 3) or (3, 5) or (3, 6) or (4, 4) 이 경우엔 직접 손으로 해보거나 brute force 를 돌려야 한다. 해보면 이 경우의 답도 역시 n*m - n*m/2 다.