[알고리즘/파이썬] 백준 알고리즘 1783번, 병든 나이트

알고리즘 풀기만 하고 정리를 하지 않으니, 어떻게 풀었는지에 대한 기억이 남질 않아서 간단한 문제푸터 정리해 볼까 한다. (ㅋㅋㅋ)

하루에 몰아풀지말고 꾸준히좀 풀어야지..

---

문제 출처 : www.acmicpc.net/problem/1783

1783번: 병든 나이트

문제 정리

이 문제에서 나이트가 이동할 수 있는 방법은 다음 네가지 뿐이다.

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

나이트는 N x M 크기의 체스판의 가장 왼쪽 아래에서 시작하며, 위의 방법을 이용하여 이동할 수 있다. 이때 나이트가 갈 수 있는 최대의 칸을 구하면 된다. 단 나이트가 5칸 이상을 방문 할 경우 위의 모든 방식을 한 번씩은 이용해야 한다.

 

문제 풀이

문제 풀이는 조건에 따라 식을 짜주어 풀었다. 해당 문제의 경우 나이트는 한 번 이동할 때 반드시 오른쪽으로 이동하므로, 중복되는 칸이 없으며 높이가 확보 된다면, 가로길이에 따라서 갈 수 있는 칸 수가 정해진다. 

따라서 높이에 따라, 높이가 3이상인 경우, 2인 경우, 1인 경우로 나누어서 생각해 볼 수 있다.

 

1. 높이가 3 이상인 경우
   • 높이가 3 이상인 경우, 나이트는 (1), (2), (3), (4) 번 방식을 모두 이용할 수 있다.
   • 따라서 가로길이가 6 보다 큰 경우, 나이트는 각 방식을 한번씩 이용할 수 있다.
   • 이때 가장 많은 칸 수를 이동하기 위해서는 오른쪽으로 한 칸씩만 이동해야 하므로, 최대로 갈 수 있는 칸 수는 (M - 6) + 4 = M - 2 칸이 된다. ( (2), (3) 으로 2칸씩 이동 하는 경우를 제외하고는 모두 한칸식 이동)
   • 가로 길이가 6보다 작은 경우, 나이트는 각 방식을 한 번씩 이용할 수 없다.
   • 이때에는 모두 (1), (4) 번을 이용하여 한칸씩 최대 4번까지 이동하는 것이 최대로 움직일 수 있는 방법이다.
   • 따라서 가로길이가 4 이상 6 미만인 경우 최대 4칸까지 움직일 수 있으며, 4보다 작은 경우 가로 칸 수 만큼 이동할 수 있다.
2. 높이가 2인 경우
   • 높이가 2인 경우, 나이트는 (2), (3) 번 방식으로 밖에 이동할 수 없다.
   • 5칸 이상을 방문 할 경우 (1), (2), (3), (4) 번 방식을 모두 이용해야 하므로, 최대로 이동할 수 있는 칸 수는 4칸이다.
   • 따라서 가로 칸 수가 8보다 큰 경우 최대 칸 수는 4칸으로 고정되며, 8보다 작은 경우 (가로길이 + 1)을 2 로 나눈 몫이 된다.
   • 여기에서 가로길이 + 1 을 하는 이유는 가장 처음에 위치한 칸 수는 무조건 방문하기 때문이다.
3. 높이가 1인 경우
   • 높이가 1인 경우, 나이트는 어느 칸으로도 이동할 수 없고, 현재 위치한 칸만 여행할 수 있다. 따라서 이 경우 나이트가 갈 수 있는 최대 칸 수는 1칸이다.

코드

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

if N >= 3 :
	if M >= 6 :
		print(M - 2)
	else :
		if M >= 4 :
			print('4')
		else :
			print(M)
elif N == 2 :
	if M >= 8 :
		print('4')
	else :
		print((M + 1) // 2)
else : 
	print('1')

+ ) 풀다가 느낀점

• 다 풀고나서 보니 너무 분기해서 풀었나 싶었는데, 간단한 문제라서 min 과 같은 내장함수를 쓰는 것 보다 이렇게 나누는게 속도가 더 빨랐다.
• M >= 6 이나 M >= 8 같은 경우 = 을 포함하나 하지 않나 결과는 같은데, 포함할 때 연산의 횟수가 줄어들어서 실행 속도가 더 빠른 것도 볼 수 있었다.
• 종종 최적화에 대해 이야기 할 때 코드를 짜는 방식, 코드의 순서도 실행 시간에 영향을 미친다던데 이렇게 간단한 코드에서도 차이가 나는 걸 보니 신기했다.