[백준 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개 미만)에는 이동 방법에 대한 제약이 없다.

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

💡알고리즘 설계

알고있으면 좋을 것

1. 나이트는 항상 오른쪽으로 이동하므로 나이트가 체스판의 중간이나 오른쪽에서 시작하는 경우는 생각할 필요가 없다.

따라서 항상 나이트의 시작 위치는 맨 왼쪽 아래로 설정한다.

2. 나이트는 위로 이동하는 방법과 아래로 이동하는 방법을 둘 다 쓸 수 있으므로, 세로 높이 3칸 이내에서만 이동하는 것이 가능하다. (2칸 위로-2칸 아래로-2칸 위로-2칸 아래로 반복) 따라서 세로 높이는 3보다 커지면 되는 경우는 따로 고려할 필요가 없다.

 

아래 이미지에서는 표가 체크판, 노란 원이 나이트의 위치입니다.

 

1. 체크판의 세로 길이가 1일 때

나이트는 이동할 때 항상 위 혹은 아래와 오른쪽으로 이동해야하므로, 세로 길이가 1이면 가로 길이에 관계없이 늘 방문할 수 있는 칸이 1개이다.

 

2. 체크판의 세로 길이가 2일 때

 

세로 길이가 2일 때, 가로 길이가 1, 2일 경우에는 이동할 수 없고, 3 이상이 되면 2칸 마다 이동 횟수가 1 늘어난다.

가로 길이가 3일 경우 2칸, 5일 경우 3칸

=> 방문한 칸의 수 = (가로 길이+1)/2

 

그러나 방문한 칸이 4개를 넘어가면 (이동 횟수가 4번이 되면) 이전에 썼던 방법으로는 이동할 수 없다. 그러므로 방문한 칸의 수가 4보다 커지면 4가 된다

=>방문한 칸의 수 = min(4, ( 가로 길이+1)/2))

 

2. 체크판의 세로 길이가 3 이상일 때

 

체크판의 세로 길이가 3보다 커지면, 위로 2칸, 아래로 2칸 이동하는 방법으로 더 효율적으로 이동할 수 있다. 그러나 가로길이가 4보다 커지면 이동 횟수가 4번이 되기 때문에 두가지 방법만으로는 이동할 수 없다.

그러나 가로 길이가 훨씬 커지면, 이동 할 때 다른 방법도 사용할 수 있다.

세로 길이가 3, 가로 길이가 7 이상이 되면 이동 방법을 모두 사용할 수 있다. 

처음 7칸을 이용해 4가지 이동 방법을 모두 사용하여 5칸을 방문하고, 이후로는 가로길이 1칸당 1칸을 더 방문할 수 있다

=> 방문한 칸의 수 = 가로 길이 - 7 + 5

 

이렇게 체크판의 세로 길이가 1일때, 2일때, 3이상일때로 나누어 코드를 짤 수 있다.

💡코드

import sys
input = sys.stdin.readline

N, M=map(int,input().split())

answer=0

if N==1:
    answer=1
elif N==2:
    answer=min(4,(M+1)//2)
else:
    if M<7:
        answer=min(4, M)
    else:
        answer=M-7+5

print(answer)

 

💡 느낀점 or 기억할 정보

완성된 코드는 짧게 나왔지만, 생각할 거리가 많아서 재밌는 문제였다!

체크판 설명 이미지는 피그마를 이용해 제작했습니다