[그리디 알고리즘] 백준 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보다 작거나 같은 자연수이다.

---

출력

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

 

---

예제 

예제 입력 1	예제 출력 1
100 50	48
예제 입력 2	예제 출력 2
1 1	1
예제 입력3	예제 출력3
17 5	4
예제 입력4	예제 출력4
2 4	2
예제 입력5	예제 출력5
20 4	4

---

아이디어

이동 횟수가 4번보다 적은 경우와 이동 횟수가 4번 이상인 경우를 분리하여 문제를 해결해야 한다. 이동 횟수가 4번이기 위해(모든 이동 방법을 한 번씩 사용한 경우) 체스판은 최소 3X7크기여야 한다.

나이트를 4번 이동시킬 수 있는 체스판 중 가장 크기가 작은 체스판 3x7

만약 체스판의 N이 3보다 작거나 M이 7보다 작은 경우 이동 횟수가 4번이 되지 않는 경우로 간주(4번 이상 이동할 수 있더라도 이동 방법을 모두 사용할 수 없으므로)하여 문제를 해결한다. 
체스판의 N이 3보다 크고 M이 7보다 큰 경우 4번 이상 이동할 수 있다. 나이트는 위, 아래로 움직일 수 있기 때문에 N이 3보다 크다면 제한 없이 움직일 수 있어 이동 경로에 영향을 주지 않는다. M은 오른쪽으로만 이동할 수 있기 때문에 이동 경로에 영향을 주게 된다. 4번의 경우를 한 번씩은 사용해야 하기 때문에 오른쪽으로 두 칸 움직이는 2,3번 이동을 한 번씩 하고 나머지는 오른쪽으로 한 칸씩 움직이는 1,4번 이동을 반복한다.

---

변수 설명(솔루션과 코드)

N: 체스판의 세로 크기

M: 체스판의 가로 크기

scount: 이동 가능한 최대 횟수 출력

---

솔루션

체스판의 세로가 3보다 작거나 7보다 작은 경우를 1) N이 1인 경우, 2) N이 2인 경우 3) N>=3, M <7인 경우로 분할한다.

1) N이 1인 경우

위아래로 한 칸도 움직일 수 없으므로 현재 나이트가 존재하는 칸 외 이동 가능한 칸이 없다. 따라서 scount = 1

2) N이 2인 경우

위아래로 한 칸씩 움직일 수 있다. 따라서 가로로 2칸씩 몇 번 이동할 수 있는지 계산해보면 M에서 현재 있는 1을 제외한 후 2로 나눈 값만큼 이동이 가능하다. 이동 가능 횟수는 최대 3번(4번 이상 이동 시 4가지 이동 방법을 모두 사용해야 하기 때문)이므로 이동 가능 횟수는 3과 (M-1)//2 중 작은 값이 된다. 나이트가 방문한 칸 수 = 이동 가능 횟수 + 1이므로 나이트가 방문한 칸 수는 4와 (M-1)//2+1 중 작은 값과 같다. (나이트가 방문한 칸 수 = 이동 가능 횟수 +1인 이유는 이동하면서 오른쪽으로 무조건 한 칸 이상 움직여야 하므로 여행 중 동일한 칸을 중복하여 방문할 수는 없기 때문이다. 따라서 첫 번째 칸과 이동 중 방문한 칸(=이동 횟수)을 더한 값과 나이트가 방문한 칸 수는 동일하다.)

3) N >=3 , M <7인 경우

N이 3과 같거나 3보다 크기 때문에 세로로는 위, 아래 두 칸씩 이동이 가능하므로 최대로 이동하기 위해서는 오른쪽으로 한 칸씩만 이동한다. 오른쪽으로 한 칸씩 이동하는 경우 최대 이동 횟수는 M-1이다. 하지만 최대 이동 횟수는 3보다 큰 값을 가질 수 없다. (4번 이상 이동 시 4가지 이동 방법을 모두 사용해야 하기 때문) 따라서 이동 가능 횟수는 3과 M-1 중 작은 값과 같으며 방문한 칸 수는 4와 M 중 작은 값과 같다.

4) N이 3보다 크거나 같고, M이 7보다 크거나 같은 경우

1. 2칸 위로, 1칸 오른쪽

2. 1칸 위로, 2칸 오른쪽

3. 1칸 아래로, 2칸 오른쪽

4. 2칸 아래로, 1칸 오른쪽

N이 3보다 크거나 같다면 위, 아래로 이동할 수 있기 때문에 이동 경로에 영향을 주지 않게 된다. 하지만 나이트가 오른쪽으로만 이동하기 때문에 4가지 이동 방법 중 1,4번의 이동을 반복하는 것이 최대 이동 횟수를 만들기에 유리하다. 하지만 2,3번 이동 또한 한 번은 이루어져야 하기 때문에 이동 횟수는 (2(2,3번 이동 1회씩)+(M-5)(M에서 나이트가 처음 있던 한 칸과 2,3번 이동으로 인한 4칸을 뺀 값))이며 최대 방문 가능한 칸 수는 이동 횟수 +1이다.

---

코드(Python)

N, M = map(int, input().split())
if N == 1:
    scount = 1
elif N == 2:
    scount = min(4, (M-1)//2 + 1)
elif M < 7:
    scount = min(4, M)
else:
    scount = (2 + (M-5)) + 1
print(scount)

 

설명에 잘못된 부분이 있거나 질문 사항이 있으시다면 언제든지 댓글 남겨주세요 :)