1783번 병든 나이트 파이썬
문제
병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.
- 2칸 위로, 1칸 오른쪽
- 1칸 위로, 2칸 오른쪽
- 1칸 아래로, 2칸 오른쪽
- 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)조건 분기가 굉장히 빡셌고, 처음에 감을 못 잡아서 블로그들에서 어떻게 문제에 접근했는지 훑었다.
그리고 스스로 조건들을 나눠봤는데, 물론 노가다로 할 수 있지만 다 하고 나니 구현 빡센 문제만큼 힘이 들었다...
목표
- 최대로 많이 방문할 수 있는 최댓값을 구하는 것
이동방식:
- 2칸 위로, 1칸 오른쪽
- 1칸 위로, 2칸 오른쪽
- 1칸 아래로, 2칸 오른쪽
- 2칸 아래로, 1칸 오른쪽
이동방식 제약:
- 1번,4번: N이 3 이상이고 M이 2 이상일 때 사용 가능
- 2번,3번: N이 2 이상이고 M이 3 이상일 때 사용 가능
특징:
- 1-4번의 특징이 상하좌우에서 '좌'만 없다.
- 모든 이동방식에 오른쪽은 꼭 끼어있다.
위의 두 이유 때문에 빙빙 도는 일 없이 무조건 체스판의 종점에 도착하게 된다.
제약:
- 이동횟수가 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칸)
