99클럽 7일차 TIL (240728)

오늘의 문제 : 하노이의 탑

 

오늘의 회고

- 하노이의 탑은 DP 대표적인 유형.. 1 부터 N-1번째 원판을 2번 기둥으로 옮기면 N번째 원판을 3번 기둥으로 옮기고 2번기둥의 원판을 3번 기둥으로 옮기면 된다. 재귀의 유형

 

문제 풀이

 1. python

def solution(n):
    answer = []
    
    def hanoi(a, b, n) :
        if n == 1 :
            answer.append([a,b])
            return
        
        hanoi(a, 6-a-b, n-1)
        answer.append([a,b])
        hanoi(6-a-b, b, n-1)
    
    hanoi(1, 3, n)
    
    return answer