📝 문제
💡 병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다.
병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.
2칸 위로, 1칸 오른쪽
1칸 위로, 2칸 오른쪽
1칸 아래로, 2칸 오른쪽
2칸 아래로, 1칸 오른쪽
병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다.
병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다.
이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.
체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자.
⚙️ 입력 : 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다.
N과 M은 2,000,000,000보다 작거나 같은 자연수이다.
⚙️ 출력 : 병든 나이트가 여행에서 방문할 수 있는 칸의 개수중 최댓값을 출력한다.
1783번: 병든 나이트
첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
✅ 풀이
n, m = map(int, input().split())
print(1 if n==1 else min(4,(m-1)//2+1) if n==2 else min(4,m) if m<=6 else m-2)💡 n이 1일 경우, 이동이 불가하므로 1이다.
n이 2인 경우는 이해가 잘 안되는 바람에 그림을 좀 그려서 풀었다.
이 경우는 위, 아래로 한 칸 갔다 오는 방법을 반복하며 홀수번 칸만 지나가기 때문에,
4회에 걸리지 않는 선에서 가장 큰 횟수를 구해주면 된다.
n이 2보다 크면, 위 아래 이동에는 제한이 없기 때문에 가로로 1칸씩만 가도록 하면 된다.
따라서 4회에 걸리지 않는 선에서 가로 길이를 고려해주면 된다.
단, 1번부터 4번까지 방법을 모두 지나갔을 경우 오른쪽으로 진행 가능한 6칸을 넘어가면 안된다.
6칸을 넘어갔을 경우, 이동이 자유분방해진다.
대신 1번부터 4번까지를 모두 한번씩 진행해야 한다.
이 때 1번부터 4번까지 지나갔다고 치면 오른쪽으로 총 7칸 진행한 것이기 때문에,
5칸 진행한 후 남은 m-7 만큼의 거리가 나머지 가로 길이다.
따라서 m-7 가지의 지점에 앞서 지나간 5칸을 더해주면 된다.
