[백준] 1783 병든 나이트 (Python 파이썬)

www.acmicpc.net/problem/1783

1783번: 병든 나이트

문제 설명

병든 나이트는 보통 체스의 나이트와는 다르게 아래의 네가지 방법으로만 움직일 수 있다.

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

이 때, 맵의 크기가 N * M으로 주어질 때, 병든 나이프가 방문할 수 있는 칸의 최대 개수를 구하면 된다.

(단, 이동 횟수가 4번 이상이라면, 4가지 방법을 한 번씩 모두 사용해야 한다.)

---

풀이 과정

병든나이트는 이동 시, 무조건 오른쪽으로는 이동을 하게 되어있고, 위 아래로는 자유인 상황이다.

 

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+1))
elif m <= 6:
    print(min(4, m))
else:
    print(m-2)

 

https://github.com/HongEunho

HongEunho - Overview

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !