양의 정수 $m$, $n\ge m$에 대해 가로 $m$칸, 세로 $2n$칸인 바둑판에 아래 4개의 조건을 동시에 만족하게 $1\times 2$나 $2\times 1$ 크기의 도미노를 최대한 많이 올려놓을 때 그 최댓값을 구하여라.
(i) 각 도미노는 바둑판에서 정확히 두 개의 서로 이웃한 칸을 덮는다.
(ii) 도미노 둘이 겹치지는 않는다.
(iii) 도미노 둘이 $2\times 2$ 정사각형을 만들지 않는다.
(iv) 바둑판의 제일 아랫줄은 정확히 $n$개의 도미노로 덮여있다.