BOJ: 1783
문제
병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.
- 2칸 위로, 1칸 오른쪽
- 1칸 위로, 2칸 오른쪽
- 1칸 아래로, 2칸 오른쪽
- 2칸 아래로, 1칸 오른쪽
병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.
체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자.
입력
첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다.
출력
병든 나이트가 여행에서 방문할 수 있는 칸의 개수중 최댓값을 출력한다.
Solution
입력 구현
1 | import sys |
케이스 분류 후 결과 출력
1 | if N > 2: |
N == 1
: 이동이 불가하여 결과가 1이므로 1 출력N == 2
: 4번보다 이동 횟수가 적을 경우M
의 길이에 따라 달라지므로(M + 1) // 2
를, 많을 경우 4를 출력N > 2
M <= 6
: 4번보다 이동 횟수가 적을 경우M
의 길이에 따라 달라지므로M
을, 많을 경우 4를 출력M > 6
: 4가지 이동 방식을 모두 사용하고 우측 방향으로 1칸 씩 이동한 결과M - 2
출력