병든 나이트 (백준 - 1783번)

그리디 알고리즘을 사용하는 문제였다.

 

우선 나이트의 모든 이동방법이 위, 아래 오른쪽으로 무조건 1칸 이상 움직이므로, 세로 길이가 1인 체스판의 경우에 나이트는 한번도 이동 할 수 없다.

 

즉 세로가 1일때는 방문한 최대 칸 수는 1칸이다.

 

이제 이동 횟수가 4번 미만일 경우를 먼저 생각해보자. 이동 횟수가 4번 미만일 경우에는 이동방법에 제한이 없다는 것을 생각하고 다음을 살펴보자.

 

우선 세로 길이가 2인 체스판의 경우이다. (2 X 5)

 

최대로 방문할 수 있는 방법은 위 그림처럼 이동방법 2, 3번을 이용하여 가로 홀수 칸을 방문하는 방법이다. 이 방법을 사용하면 체스판의 가로 길이가 M이라고 했을때 나이트는 최대 (M + 1) / 2 칸을 방문할 수 있다. 하지만 위 규칙에 따라 이동횟수는 4번 미만이여야 한다. 즉, 방문할 수 있는 칸이 최대 4칸이다.

 

그러므로 (M + 1) / 2칸과 4칸 중에 작은 값이 세로 2, 가로 M에서 나이트가 최대로 방문할 수 있는 칸 수이다.

 

다음은 가로 길이가 7미만이고 세로 길이가 3이상일 경우이다. (왜 7미만인지는 후술한다) (3 X 5)

 

이 경우 세로 길이가 3을 넘어서기 때문에 이동방법의 제약을 무시하고 최대로 방문할 수 있는 방법은 위 그림처럼 1, 4번 방법을 이용하여 방문이 가능하다. 앞의 예제와는 다르게 위아래로 2칸씩 이동 할 수 있어졌기 때문에 가로칸를 한칸씩 방문이 가능하다. 가로 길이가 M이라고 했을때 나이트는 최대 M칸을 방문할 수 있다. 하지만 역시 이동방법의 제약을 무시하므로 최대 방문할 수 있는 칸은 4칸이다.

 

그러므로 M칸과 4칸 중에 작은 값이 세로 3이상, 가로 M에서 나이트가 최대로 방문할 수 있는 칸 수이다.  

 

이제 이동 횟수가 4칸 이상일 경우를 살펴보겠다. 여기서는 위에 있는 4가지의 이동방법을 모두 사용하며 이동해야 한다는 제약이 있으므로 이것을 생각하고 살펴보도록 하자.

 

다음은 가로 길이가 7이상이고 세로 길이가 4이상일 경우이다. 최소 이정도 칸을 확보해야 모든 이동방법을 사용할 수 있다. (7 X 7)

 

모든 이동방법을 사용하여 방문하려면 가로가 최소 7칸이 필요하다. 가로가 7칸일 경우 방문하는 최대 칸은 총 5칸이다. 모든 이동방법을 사용했기 때문에 8칸 부터는 제약이 없다. 8칸 부터는 최대 가로길이가 M일때 M - 7만큼 방문할 수 있다.

 

그러므로 세로 4이상, 가로가 M일 경우에 방문하는 최대 칸 수는 앞에 모든 이동방법을 사용하는 5칸과 그 이후 방문할 수 있는 M - 7을 더하여 M - 7 + 5가 된다. 

 

모든 조건을 정리하면 다음과 같다.

 

• 세로가 1일때 방문할 수 있는 최대 칸수는 1이다.
• 세로가 2일때 방문할 수 있는 최대 칸수는 4와 (M + 1) / 2 중 작은 값이다.
• 가로가 7미만일때 방문할 수 있는 최대 칸수는 4와 M 중 작은 값이다.
• 그외 체스판 경우에 방문할 수 있는 최대 칸수는 M - 7 + 5이다.

 

코드는 다음과 같다.

#include <iostream>
using namespace std;

int min(int a, int b)
{
	return a < b ? a : b;
}

int main()
{
	int N, M;
	cin >> N >> M;
	
	if (N == 1)
		cout << 1 << endl;
	else if (N == 2)
		cout << min(4, (M + 1) / 2) << endl;
	else if (M < 7)
		cout << min(4, M) << endl;
	else
		cout << M - 7 + 5 << endl;

}