[백준 1783 - 병든 나이트]

문제
병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.

1. 2칸 위로, 1칸 오른쪽
2. 1칸 위로, 2칸 오른쪽
3. 1칸 아래로, 2칸 오른쪽
4. 2칸 아래로, 1칸 오른쪽

병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.

체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자.

입력
첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다.

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

예시 1

예시 2

예시 3

예시 4

예시 5

분석 내용
N = 1일 때, 한 칸도 움직일 수 없으므로 이동할 수 있는 칸이 없다. 따라서, 나이트가 존재하고 있는 칸을 포함하여 방문 가능한 칸은 1개이다.

N = 2일 때, 위 아래로 한 칸씩 움직일 수 있기 때문에 2번과 3번의 방법대로 이동이 가능하다. 오른쪽으로 2칸씩 이동해야한다는 것을 생각했을 때 (M-1)//2 칸 만큼 이동이 가능하다는 것을 알 수 있고, 현재 존재하고 있는 칸의 개수를 포함해서 (M-1)//2 + 1의 칸을 방문할 수 있다.

N => 3 그리고 N < 7일 때, 오른쪽으로 한 칸씩 이동하는 경우에 최대 이동 횟수를 구할 수 있다. 이 경우 방문할 수 있는 칸의 개수는 M과 같다.

M > 7일 때, 네 가지 방법을 모두 사용해야하지만, 최대 이동 칸 수를 구하기 위해서는 1번과 4번을 반복하는 것이 좋다. 2번과 3번을 1번씩 사용했다고 생각했을 때를 구하면, M-5 + 2 + 1칸을 방문할 수 있다.

코드 구현(python 언어)

N, M = map(int, input().split()) #두 개의 정수 입력 받기

if N == 1: #N이 1일 때
	 count = 1 
elif N == 2: #N이 2일 때
	count = min(4, (M-1)//2 + 1) 
elif M < 7: #N>=3 그리고 N<7 일 때
	count = min(4, M) 
else: #N >= 7일 때
	count = M-5 + 2 + 1 
    
print(count)

궁금한 점

1) 이동 가능 횟수가 최대 4번이 되는 이유를 모르겠다.