[백준] 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) 문제를 살펴보면 병든 나이트는 오른쪽으로는 무조건 이동해야 하지만, 위,아래로는 최대 3칸 안에서 움직일 수 있다. 즉, N값이 3이상인 경우에는 N값이 결과값에 영향을 미치지 않는다는 말이다.
2) 문제의 조건을 모두 만족시키면서 가질 수 있는 N과 M의 최솟값을 구해보자.
-> N = 4, M = 7일때, 모든 조건을 만족시키고 칸의 최대 개수는 5가 된다.
3) 1)과 2)를 통해 N값은 3, M값은 7을 기준으로 경우의 수를 생각해봐야 한다는 사실을 도출해낼 수 있다.

아이디어 구체화

1) N 혹은 M값이 1이라면 1이 최대 개수
2) N이 2인 경우
- M이 3미만 => 1이 최대
- M이 3이상 5미만 => 2가 최대
- M이 5이상 7미만 => 3이 최대
- M이 7이상 => 4가 최대 (모든 방법을 사용할 수 없기 때문에, 최대 개수는 4)
3) N이 3이상인 경우
- M이 4미만 => M값이 최대
- M이 4이상 7미만 => 4가 최대
- M이 7이상 => 5+(M-7) = M-2

M이 7일 때 처음으로 모든 방법을 사용하면서 최대개수가 5가 되는 시점이기 때문에, M이 7이상인 구간에 대해서는 1회씩 증가되기 때문에 5+(M-7)이 되는 것이다.

코드

N, M = map(int,input().split())

if N == 1 or M == 1:
    print(1)
elif N == 2:
    if M < 3:
        print(1)
    elif 3 <= M < 5:
        print(2)
    elif 5 <= M < 7:
        print(3)
    else:
        print(4)
elif N >= 3:
    if M < 4:
        print(M)
    elif 4 <= M < 7:
        print(4)
    else:
        print(M-2)