프로그래머스 하노이의 탑 (파이썬 풀이)

https://programmers.co.kr/learn/courses/30/lessons/12946?language=python3 

코딩테스트 연습 - 하노이의 탑

 

내가 한 풀이

n=1일 경우

1번 탑에서 3번 탑으로 이동 = 1

 

n=2일 경우

1번 탑에서 1번째 판 2번 탑으로 이동

1번 탑에서 2번째 판 3번 탑으로 이동

2번 탑에서 1번째 판 3번 탑으로 이동 

=> n=1일 경우 3번 반복

 

n=3일 경우

1번 탑에서 1,2번째 판 2번 탑으로 이동 => n=2일 경우

1번 탑에서 3번 판 3번 탑으로 이동 => n=1일 경우

2번 탑에서 1,2번째 판 3번 탑으로 이동 => n=2일 경우

 

일반화를 하면

n개의 판을 옮기는 방법은

n-1개 판 2번 탑으로 옮기는 경우+1개 판 3번 탑으로 옮기는 경우+ n-1개 판 3번 탑으로 옮기는 경우 이다.

따라서 재귀함수를 이용해 문제를 해결해야 한다.

def hanoi(n,start,end,mid):
    global answer
    if n==1:
        answer.append([start,end])
    else:
        hanoi(n-1,start,mid,end)
        answer.append([start,end])
        hanoi(n-1,mid,end,start)
def solution(n):
    
    global answer
    answer = []
    hanoi(n,1,3,2)
    return answer