[백준] : (Python)

문제📖

풀이🙏

• 막대 번호를 1, 2, 3 이라고 지정한다.
• hanoi_tower에서 먼저 막대 2번으로 n-1개의 기둥을 보내고 3번으로 1개를 보낸 후에 다시 n-1개를 2번에서 3번 막대로 이동하는 것을 파악했다.
• f(n) = 2*f(n-1) + 1
• 재귀적으로 hanoi_tower 함수를 이용하여 막대를 옮긴다.

코드💻

def hanoi_tower(n, start, end):
    if n == 1:
        print(start, end)
        return

    # 막대 번호 1,2,3 이므로 총 6
    # 3개의 막대만 있으므로 가능
    # 6 - start - end = 번호 모를 막대 번호 
    hanoi_tower(n-1, start, 6-start-end)
    print(start, end)
    hanoi_tower(n-1, 6-start-end, end)

n = int(input())
print(2**n-1) # 총 이동 횟수
hanoi_tower(n, 1, 3)