12월의 퍼즐에 참여해주신 모든 분들께 감사드립니다!
12월의 정답자로 선정되신 이대근님께 소정의 기념품을 전달드릴 예정입니다.
이외 12월의 퍼즐 정답을 맞춰주신 김성안 김태훈 홍노을 이윤조님께
HORIZON 일러스트로 제작한 탁상용 달력을 선물로 전달드릴 예정입니다.
이 문제는 특별한 비법은 없고 열심히 조각을 움직여 보는 게 최선이다. 다음처럼 20번 움직이는 것이 최소이다. 물론 20번 움직이는 것은 이 방법 외에 다른 방법도 가능하다.
(위 경우 카드의 이동순서는 다음과 같다: Merry-Xmas-Horizon-from-to-Merry-Xmas-Horizon-from-to-Merry-Xmas-Horizon-KIAS-You-Merry-Xmas-from-KIAS-HORIZON)
보너스 문제의 경우, 처음에 배열된 순서는 7-6-5-4-3-2-1이다. 이때 각 수마다 그 뒤에 있으면서 그 수보다 작은 수의 개수를 세어서 모두 더한 값을 반전수inversion number라 하자. 7 뒤에는 7보다 작은 수가 6개, 6 뒤에는 6보다 작은 수가 5개, …, 2 뒤에는 2보다 작은 수가 1개 있으므로, 이 배열의 반전수는 \(6+5+\dots+1 = 21\)이 된다. 카드 하나를 좌우로 움직이는 것은 반전수를 바꾸지 않는다. 카드 하나를 곡선을 따라 움직이면 두 칸 이동하므로 반전수는 짝수만큼만 바뀌게 된다. 따라서 카드를 어떻게 움직여도 반전수는 언제나 홀수이다.
만약 보너스 문제의 배열을 1-2-3-4-5-6-7로 바꿀 수 있다면, 이때 반전수는 0이 되므로 결국 7-6-5-4-3-2-1을 1-2-3-4-5-6-7로 바꾸는 것은 불가능하다.
다음은 12월의 정답자로 선정된 이대근님의 해설입니다.
BFS로 탐색하였습니다.
[1] 20번 만에 가능합니다.
to
KIAS
Horizon
Xmas
KIAS
Horizon
Merry
to
Horizon
from
You
Merry
to
Horizon
from
You
Xmas
to
You
from
[2] 불가능합니다.
