[코테] 백준 그리디 1783번 문제

1783번 : 병든 나이트

문제 링크

https://www.acmicpc.net/problem/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())

# 1~4의 방법을 1번씩 다 쓸 수 있는 크기 이상일 때
# 즉, N x M의 크기가 3 x 7 이상일 때 방문한 칸 수 는 M-2
if N >= 3 and M >= 7 :
    print(M-2)

    
# N의 크기가 3이고
elif N >= 3 :
    
    # 오른쪽으로 1칸씩 이동해서 최대 3번 이상 이동 가능한 크기일때
    # 즉, M이 4이상일 때 4를 출력
    if M >= 4 :
        print(4)
    
    # M이 4 미만일 때 M을 출력
    else :
        print(M)

# N의 크기가 2이고
elif N == 2 :
    
    # 오른쪽으로 2칸씩 이동해서 최대 3번 이상 이동 가능한 크기일때
    # 즉, M이 7이상일 때 4를 출력
    if M >= 7 :
        print(4)
    
    # M이 7미만일 때 M에 2를 나눈 값 + M에 2를 나눈 나머지를 출력
    else :
        print(int(M//2 + M%2))
    
# N의 크기가 1일때는 움직일 수 없기에 1 출력
else : 
    print(1)