풀이1. 재귀
count = 0
msg = []
def hanoi(num,start,mid,finish):
global count
if num == 1:
msg.append((start,finish)) # n이 하나면 경유 없이 바로 finish로 옮기기
count += 1
else:
hanoi(num-1,start,finish,mid) # n-1개 원판 2번째로 옮기기
msg.append((start,finish)) # n번째 원판 3번째로 옮기기
count += 1
hanoi(num-1,mid,start,finish) # n-1개 원판 3번째로 옮기기
n = eval(input())
hanoi(n,1,2,3)
# 출력
print(count)
for m in msg:
print(*m) # 튜플 언팩-
원리 : n개의 원판을 3번째로 옮기기 위해서는 상위 n-1개를 2번째로 옮기고 마지막 n번째 원판을 3번째로 옮기고 다시 상위n-1개 원판을 3번으로 옮겨야합니다
-
이때 n-1을 옮기는 것은 또 n-2를 옮겨야하기때문에 앞에서 한 일이 반복되어서 그것을 이용해서 재귀를 짜면됩니다.
-
원판을 옮길때는 하나일때를 제외하고는 정렬을해서 옮겨야하기때문에 중간에 하나를 경유해서 옮겨야합니다
-
튜플((3,1))을 저장하고 출력할 때는 *을 이용해서 언팩(3 1)해줍니다.
