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

출력

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

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

if N==1 or M==1:
    print(1)
elif N==2:
    print(min(4,(M+1)//2))
elif M<=6:
    print(min(4,M))
else:
    print(M-2)

조건 분기가 굉장히 빡셌고, 처음에 감을 못 잡아서 블로그들에서 어떻게 문제에 접근했는지 훑었다.

그리고 스스로 조건들을 나눠봤는데, 물론 노가다로 할 수 있지만 다 하고 나니 구현 빡센 문제만큼 힘이 들었다...

목표

• 최대로 많이 방문할 수 있는 최댓값을 구하는 것

이동방식:

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

이동방식 제약:

• 1번,4번: N이 3 이상이고 M이 2 이상일 때 사용 가능
• 2번,3번: N이 2 이상이고 M이 3 이상일 때 사용 가능

특징:

1. 1-4번의 특징이 상하좌우에서 '좌'만 없다.
2. 모든 이동방식에 오른쪽은 꼭 끼어있다.

위의 두 이유 때문에 빙빙 도는 일 없이 무조건 체스판의 종점에 도착하게 된다.

제약:

• 이동횟수가 4번보다 적다면 움직임에 제약이 업음
• 이동횟수가 4번보다 적지 않다면 꼭 이동방식 4개를 최소 한번씩은 사용을 해야 함
  • 따라서 5칸 이상을 가려면 M이 최소 7은 되야 함 (오른쪽을 다 쓰려면 1+2+2+1=6이고 시작 위치가 1이기 때문)

미리 거를 수 있는 조건:

- N이 1일 떄
- 최소 한 칸은 위로든 아래로든 가야하기 때문에, 최대 방문 가능 횟수는 현 위치인 1칸

- N이 2일 떄
- 2,3을 번갈아 사용하면서 오른쪽으로 2칸 씩 갈 수는 있지만, 1,4번을 사용 못하기 때문에 최대 방문 횟수는 4 미만.. 따라서 4랑 (M+1)//2 중 더 작은 값을 출력
- (M+1)//2인 이유: 1은 시작 지점이라서 더해준거고. 2번 3번 중 뭘 택하더라도 오른쪽으로 2칸씩밖에 못 가서 2를 나눠준것

- M이 1일 떄
- 최소 한 칸은 오른쪽으로 가야하기 때문에, 최대 방문 가능 횟수는 현 위치인 1칸

- M이 6과 같거나 작을 때
- 만약 5번 이상을 가려면 M=7일때만 가능하기 때문에 무조건 4 이하의 값이 나온다. 따라서 4랑 M 중 더 작은 값을 출력

- M이 6보다 클 때
- 위에서 조건들이 걸러지면서 N이 3 이상이라는 거는 보장된 상태라서 오른쪽으로 가는 것만 고려하면 된다.
- 다만, 최댓값을 구하려고 하되, 4를 넘기기 위해 모든 경우의 수는 사용해야 해서, 2와 3은 한번씩만 실행하고, 나머지는 오른쪽을 1칸만 가도록 한다.
- 결국 최대 방문 가능 횟수는 M- 2(이동방식 2번의 오른쪽 2칸+ 이동방식 3번의 오른쪽 2칸)