문제
병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.
- 2칸 위로, 1칸 오른쪽
- 1칸 위로, 2칸 오른쪽
- 1칸 아래로, 2칸 오른쪽
- 2칸 아래로, 1칸 오른쪽
병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자.
입력
첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다.
출력
병든 나이트가 여행에서 방문할 수 있는 칸의 개수중 최댓값을 출력한다.
예제 입력 1
100 50예제 출력 1
48예제 입력 2
1 1예제 출력 2
1예제 입력 3
17 5예제 출력 3
4예제 입력 4
2 4예제 출력 4
2예제 입력 5
20 4예제 출력 5
4
내 풀이
행 N, 열 M이라고 생각하자.
N이 3보다 작거나 M이 7보다 작은 경우를 아래와 같이 3가지로 분할한다.
1. N = 1인 경우,
🐴이 위, 아래 어떤 방향으로도 움직이지 못하므로, 현재 서있는 칸만 머무를 수 있다. 즉, answer = 1
2. N = 2인 경우,
- 🐴이 위, 아래 방향으로 1칸씩 움직일 수 있다.
- 🐴의 이동횟수가 4 이상일 경우는 4가지의 방법을 모두 사용해야 한다. (But, a에 말했던 것처럼 위, 아래 방향으로 1칸씩만 움직일 수 있으므로 이동횟수가 4이상이면 안된다.)
- 위,아래 방향으로 1칸씩 움직일 수 있으므로 오른쪽 방향으로는 무조건 2칸씩 움직여야 한다. So, (M-1) // 2 만큼 이동할 수 있다.
- 결국 🐴은 (M-1) // 2 와 3 중에서 더 작은 수 만큼 이동할 수 있으므로, 🐴이 머무를 수 있는 개수는 처음 머물고 있었던 칸의 수를 합쳐 ((M-1) // 2) + 1 와 3 + 1 중 더 작은 수 이다.
3. N ≥ 3인 경우,
🐴이 위,아래 방향으로 1칸, 2칸 모두 이동 가능하다.
So, 모든 경우의 수를 사용할 수 있다.
But, 모든 경우의 수를 한 번씩 이용하여 🐴을 이동시켜보면, M = 7이 나온다.
즉, 모든 경우의 수를 사용하기 위해서는 M ≥ 7 이어야 한다는 조건이 필요하다.
a. M < 7인 경우,
최대로 움직이기 위해서는 UUR 또는 DDR로 움직이는 것이 유리하다.
그렇다면, M-1 만큼 움직일 수 있다.
So, M-1 와 3 중에서 더 작은 수 만큼 이동할 수 있고, 머무를 수 있는 칸의 개수는처음 머물고 있었던 칸의 수를 합쳐서 M 과 4 중에서 더 작은 수 이다.
But, 이동횟수가 4 이상이면 안 된다.
b. M ≥ 7인 경우,
최대로 움직이기 위해서는 UUR 또는 DDR로 움직이는 것이 유리하다.
But, URR과 DRR도 한 번씩은 이루어져야 한다.
→ 즉, (M-1)에서 손해 본 칸 2칸을 빼주고, 처음 머물고 있었던 칸의 수를 합쳐준다
→ (M-1) - 2 + 1 = M - 2
N, M = map(int, input().split())
if N == 1:
answer = 1
elif N == 2:
answer = min((M-1)//2 + 1, 4)
elif N >= 3 and M < 7:
answer = min(M, 4)
else:
answer = M - 2
print(answer)