기록공간

그리디 알고리즘을 사용하는 문제였다. 우선 나이트의 모든 이동방법이 위, 아래 오른쪽으로 무조건 1칸 이상 움직이므로, 세로 길이가 1인 체스판의 경우에 나이트는 한번도 이동 할 수 없다. 즉 세로가 1일때는 방문한 최대 칸 수는 1칸이다. 이제 이동 횟수가 4번 미만일 경우를 먼저 생각해보자. 이동 횟수가 4번 미만일 경우에는 이동방법에 제한이 없다는 것을 생각하고 다음을 살펴보자. 우선 세로 길이가 2인 체스판의 경우이다. (2 X 5) 최대로 방문할 수 있는 방법은 위 그림처럼 이동방법 2, 3번을 이용하여 가로 홀수 칸을 방문하는 방법이다. 이 방법을 사용하면 체스판의 가로 길이가 M이라고 했을때 나이트는 최대 (M + 1) / 2 칸을 방문할 수 있다. 하지만 위 규칙에 따라 이동횟수는 4번 미..