아이디어

1. 재귀함수 이용

이 문제를 보고 가장 먼저 떠오른 풀이는 트리의 height를 구하는 함수였다.

즉, 병든 나이트가 이동한 후에 다시 재귀함수를 부르고, 또 이렇게 이동한 나이트가 다시 재귀함수를 호출하는 형식으로 최대값을 구하는 것이다.

이 방식으로 짰던 코드는 다음과 같다.

코드

int SickNight_MaxMove(int max_x, int max_y, int now_x, int now_y) {
	int num[4] = { 0, 0, 0, 0 };
	int max = 0;
	cout << "( " << now_x << ", " << now_y << " )" << endl;
	if ((now_x + 1 <= max_x) && (now_y + 2 <= max_y))
		num[0] = SickNight_MaxMove(max_x, max_y, now_x + 1, now_y + 2);
	if ((now_x + 2 <= max_x) && (now_y + 1 <= max_y))
		num[1] = SickNight_MaxMove(max_x, max_y, now_x + 2, now_y + 1);
	if ((now_x + 2 <= max_x) && ((now_y - 1 <= max_y) && (now_y - 1 > 0)))
		num[2] = SickNight_MaxMove(max_x, max_y, now_x + 2, now_y - 1);
	if ((now_x + 1 <= max_x) && ((now_y - 2 <= max_y) && (now_y - 2 > 0)))
		num[3] = SickNight_MaxMove(max_x, max_y, now_x + 1, now_y - 2);
	max = 1 + array_max(num, 4);
	return max;
}

int array_max(int a[], int size) {
	int index = 0;
	for (int i = 0; i < size; i++) {
		if (a[i] > a[index])
			index = i;
	}
	return a[index];
}

int main() {
	int a, b;
	cin >> a, b;
	cout << SickNight_MaxMove(a, b, 1, 1);
}

문제점

위와 같은 코드의 가장 큰 문제점은 병든 나이트의 이동 횟수가 4번보다 많은 경우의 예외처리가 안된다는 점이다.

물론 이것은 내 코딩 실력의 문제일 수 있을 것이다.

그렇다면 다른 어떠한 방법으로 뭐 이 예외처리를 할 수 있다고 하자.
이 경우에는 재귀함수의 가장 큰 문제가 발목을 잡게 된다.

위와 같이 짠 함수의 시간 복잡도를 계산해 보면 2의 n제곱 알고리즘이 될 것임을 예상해 볼 수 있다.

즉, 입력값 M, N중 어떤 값이 커질 경우 계산 시간이 너무 오래 걸린다는 것이다.
(본 문제의 예시처럼 입력이 100, 50일 경우만 생각해도 안될 것이다.)

2. 논리 이용

위의 오류로 인해 많은 생각을 해 본 문제였는데 결국 힌트는 이 알고리즘의 분류가 "많은 조건 분기"라는 것에서 얻었다.

1. 우선 가장 먼저 생각난 것은 본 문제는 선형적인 성질이 있다는 것이다. 즉, 나이트의 이동횟수가 4번보다 많은경우, 4가지 이동 방법을 모두 사용해야 하는데 이것은 나이트가 (7,1)에서 시작하는 것이랑 똑같다는 것이다.

2. 위의 생각이 들자 다음으로 생각난 것은 이동 방법에서 x방향은 1또는 2이지만 y방향으로의 이동은 +2, +1, -1, -2로, 만약 y의 길이가 3보다 클 경우에는 위아래로 왔다갔다 하면서 움직일 수 있겠다는 것이다.

   -> 즉, y의 길이가 3보다 클 경우에는 그 크기를 신경쓰지 않아도 될 것이다.

3. 2번 생각에서 다시한번 생각해 볼만한 것이 있다. 문제가 원하는 최대값을 구하기 위해서는 x방향으로 2를 가기보다는 1을 가야만 할 것이다.

4. 위의 생각들을 바탕으로 x의 크기에 따라 조건을 나누어 보았다. 그러자 다음과 같이 이럴수 밖에 없겠다라는 생각이 들었다.

   • 만약 체스판의 가로의 길이가 7인 경우에는 5번 방문을 할 수도 있고 4번만에 7까지 갈 수도 있을 것이다.

   • 가로의 길이가 만약 8보다 크거나 같으면 무조건 5번 이상 방문을 해야된다는 것이다.
     (세로의 길이가 충분히 크다고 생각할 때)

   • 가로의 길이가 4이하일 경우, 5일경우, 6일경우 위와 같은 방법들로 나누어 볼 수 있겠다.

5. 위와 같이 x의 조건과 더불어 y조건도 포함하면 되겠다.

해법

#include <iostream>
using namespace std;

int SickNight_MaxMove(int a, int b);

int main() {
	int a, b;
	cin >> a >> b;

	cout << SickNight_MaxMove(b, a) << endl;
    
	return 0;
}
int SickNight_MaxMove(int max_x, int max_y) {
	if (max_x <= 4) {
		if (max_y >= 3)
			return max_x;
		else if (max_y == 2)
			return (max_x+1)/2;
		else
			return 1;
	}
	else if (max_x == 5 || max_x == 6) {
		if (max_y >= 3)
			return 4;
		else if (max_y == 2)
			return 3;
		else
			return 1;
	}
	else if (max_x == 7) {
		if (max_y >= 3)
			return 5;
		else if (max_y == 2)
			return 4;
		else
			return 1;
	}
	else {
		if (max_y >= 3)
			return max_x - 2; // 4+(max_x-6)
		else if (max_y == 2)
			return 4;
		else
			return 1;
	}
}

int main() {
	int a, b;
	cin >> a, b;
	cout << SickNight_MaxMove(a, b);
}