문제 요약

병든 나이트가 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다.

조건:
if 이동 횟수 <= 4번, then 이동 방법을 모두 한 번씩 사용
else 제약 X

가능한 이동 방법:

A. 2칸 위로, 1칸 오른쪽
B. 1칸 위로, 2칸 오른쪽
C. 1칸 아래로, 2칸 오른쪽
D. 2칸 아래로, 1칸 오른쪽

입력
N,M <= 2,000,000,000인 자연수

출력
병든 나이트가 여행에서 방문할 수 있는 칸의 개수중 최댓값

풀이

문제 이해하는데 시간이 많이 걸린 문제이다.
문제를 정확히 이해한다면 크게 어려울 것 없지만, 문제 설명이 이해하기 힘든 부분이 있다.

우선 구하고자 하는 것은 한 번의 여행으로 할 수 있는 최대 이동 수이다.
나는 처음에 가능한 모든 경우의 수를 구하는 문제인 줄 알고 DP로 접근하려 했으나, 입력값이 20억보다 작은 자연수인 것을 보고 그것이 아님을 깨달았다.

한 가지 조건이 더 있으니 살펴보겠다.
바로 이동횟수가 4번보다 작지 않다면 이동 방법을 한 번씩 사용해야한다는 것이다.
4번보다 작은 경우는 예제 케이스인 2 5에서 잘 드러나는데, 이처럼 아무리 움직이려해봐도 4번보다 클 수 없는 경우를 말하는 것이다. 또 다른 케이스는 3 3이 있을 것이다. (2번의 움직임, 출력: 3)

풀이는 간단하다.
예외처리를 해주고, 그 외의 경우에는 m-2를 출력하는 것이다.
이유는 다음과 같다.

• 나이트는 왼쪽으로는 이동할 수 없다.
• 따라서 오른쪽으로 움직이는 횟수를 최소화하며 움직이면 그것이 이동의 최댓값이다.
• 그렇기 때문에 A. 2칸 위로 1칸 오른쪽 과 D. 2칸 아래로 1칸 오른쪽 을 최대로 이용해야한다.
• 그러므로 B. 1칸 위로, 2칸 오른쪽 과 C. 1칸 아래로, 2칸 오른쪽 을 한 번만 사용하고 나머지는 A, B로 움직여야 한다.

코드:

#include <iostream>
using namespace std;

int main()
{
	int n, m, ans;

	cin >> n >> m;
	if (n == 1)
		ans = 1;
	else if (n == 2)
		ans =  min(((m - 1) / 2) + 1, 4);
	else if (m < 7)
		ans = min(m, 4);
	else
		ans = m - 2;
	cout << ans;
}