[백준] 11729번 하노이 탑 이동 순서

문제 출처 : https://www.acmicpc.net/problem/11729

정답 코드 💻

n = int(input())

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

    hanoi(n-1,start,6-start-end) # 세 막대의 합이 6
    print(start,end)
    hanoi(n-1, 6-start-end, end)

print(2**n-1)
hanoi(n,1,3)

👉🏻 재귀함수를 이용해서 하노이 탑을 이동해야 했다.

설명

👉🏻 start와 end 막대 번호만 알뿐 나머지 막대 번호는 모르지만 모든 막대의 번호 합이 6이므로 6-start-end를 하면 막대의 번호를 알 수 있다.
👉🏻 n-1개씩 재귀함수를 이용하면 구할 수 있다.

느낀 점 ✏️

특히 마지막 개수가 2**n -1 이걸 생각하다니... 역시 어렵다... 다음은 브루트 포스 파이팅!