백준 1783번 - 병든 나이트

출처 : 1783번: 병든 나이트 (acmicpc.net)

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보다 작거나 같은 자연수이다.

출력

병든 나이트가 여행에서 방문할 수 있는 칸의 개수 중 최댓값을 출력한다.

 

---

[ 문제 설명 ]

 

그림으로 설명하겠습니다.

 

이문제는 원리는 찾고 그것을 코딩하는 방식이 dp에 가깝군요. 

알고리즘 분류는 그리디와 가깝지만요.

 

아무래도 공식을 찾아나가는 과정이 그리디와 유사해서가 아닌가 쉽습니다.

 

그림 1 - 병든 나이트 설명

그림 2 - 병든 나이트 설명

---

[ 코드 ]

 

n, m = map(int, input().split())


if n == 1:
    print(1)
elif n == 2:
    k = int((m + 1) // 2)
    print(min(k, 4))
elif m < 7:
    print(min(4, m))
else:
    print(m-7 + 5)

 

---

후기

 

사실 이문제는 나이도는 체감상 더 어렵다고 느껴지는데

왜 이렇게 쉽게 책정되었는지 모르겠습니다.

물론 코드는 쉽습니다.

하지만 이코드를 만드는 과정이 쉽다고 한다면 모르겠네요.