[Baekjoon] 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보다 작거나 같은 자연수이다.

출력

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

예제

Example 1:

Input: 
100 50
Output: 
48

Example 2:

Input:
1 1
Output:
1

Example 3:

Input:
17 5
Output:
4

Example 4:

Input:
2 4
Output:
2

Example 5:

Input:
20 4
Output:
4

조건

시간 제한 : 2초

메모리 제한 : 128 MB

풀이과정

내 풀이

n, m = map(int,input().split())
# 4번보다 같거나 적은 경우에는 제약이 없음.
# 4번보다 많다면 이동 방법을 모두 한 번씩 사용해야 한다.

ans = 1
if n == 1:
    print(ans)
elif n == 2:
    ans += (m-1)//2
    if ans >= 4:
        print("4")
    else:
        print(ans)
# n >= 3
else:
    if m >= 7:
        ans += 4
        print(ans+(m-7))
    else:
        ans += m-1
        if ans >= 4:
            print("4")
        else:
            print(ans)

여러 케이스르 나누어서 풀이하였다. 4가지방법은 모두 오른쪽으로만 움직이므로 세로길이를 기준으로 나눈다.

1. 세로가 1이라면 움직일 수 없으므로 1을 출력한다.
2. 세로가 2라면 위아래 1칸씩 움직일 수 있다. 이 경우를 모두 세는 대신에, 4를 넘어서면 4를 출력한다.
3. 세로가 3이상이라면 위아래로는 4가지방법을 다 사용할 수 있다. 여기서 가로가 7이상이라면 4가지 방법을 다 사용할 수 있으므로 4를 더해주고, 1칸씩 가는것이 최대치이므로 m-7를 더해준다. 여기서 7미만이라면 4가지방법을 사용하지 못한다. 1칸씩 가는 것이 최선이므로 m-1을 더해주고 2와 같은 방식으로 출력한다.