문제
https://www.acmicpc.net/problem/27512
풀이
- 격자의 가로 길이
n과 세로 길이m이 주어질 때, "최적의 전략"을 유지할 수 있는 가장 긴 뱀의 길이를 출력
여기서 가장 긴 뱀의 길이는 시작점과 끝점이 인접하면서 모든 칸을 방문한 길이입니다.
단순히 모든 칸의 개수만 구하면 될 것 같지만, 시작점과 끝점이 인접해야한다는 조건 때문에 칸의 개수만 구하면 올바른 답이 나오지 않습니다.
위 그림과 같이 n과 m이 모두 짝수일 경우에는 모든 칸을 방문할 수 있습니다.
위 그림과 같이 n이 짝수 m이 홀수인 경우에도 모든 칸을 방문할 수 있습니다.
n과 m이 모두 홀수인 경우에는 한 칸을 제외하고 모두 방문할 수 있습니다.
가장 긴 뱀의 길이를 구하기 위해서는 n과 m 모두 홀수인 경우를 제외한 경우는 n과 m을 곱한 넓이를 리턴하고 홀수인 경우에는 곱한 값에서 1을 빼주면 올바른 답이 리턴됩니다.
코드
import sys
input = sys.stdin.readline
def snake(n,m):
return n * m - 1 if n % 2 != 0 and m % 2 != 0 else n * m
if __name__ == "__main__":
n,m = map(int,input().split())
print(snake(n,m))