(Python) - BOJ(1783번) : 병든 나이트

 

https://www.acmicpc.net/problem/1783

1783번: 병든 나이트

---

• 해설 : 

 

병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.

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

병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.

체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구하는 문제이다.

 

 

 

---

• 풀이 :

1. 세로나 가로의 길이가 1이라면 시작 칸 밖에 방문하지 못한다.

 

2. 세로의 길이가 2일 경우, 선택권은 2,3 방법 밖에 없다. ( 세로로 한칸씩만 움직이는 방법 )

   이 때는, 가로의 길이가 아무리 길어도 4번이상 움직이지 못하므로, 최댓값은 4가 될 것이다.

   

3. 가로의 길이가 6이하일 경우에, 4번 이상으로 움직인다고 하면, 1~4번 방법을 모두 써야 하므로 최댓값은 4가 될 것이고, 최소값은 자신 가로의 길이가 될 것이다.

 

4. 세로의 길이가 3 이상이고, 가로의 길이가 7이상인 경우에는 이동에 제약이 없으므로 오른쪽으로 두 칸을 가야만 하는 강제적인 방법을 빼고는 한칸씩만 움직이면 되므로 m-2 라는 값이 나오게 된다.

 

 

 

---

• 소스코드 : 

 

n, m = map(int, input().split())
if n == 1:
    print(1)
elif n == 2:
    print(min(4, (m + 1) // 2))
else:
    if m <= 6:
        print(min(4, m))
    else:
        print(m - 2)