프로그래머스::하노이의 탑

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12946

난이도 : Lv.2

 

풀이

def solution(n):
    return hanoi(1, 2, 3, [], n)
    
def hanoi(src, tran, dst, trace, n):
    if n == 1:
        trace.append([src, dst])
        return
    hanoi(src, dst, tran, answer, n - 1)
    trace.append([src, dst])
    hanoi(tran, src, dst, answer, n - 1)
    return trace

재귀 문제에서 자주 나오는 문제이다.

간단하게 생각해서

1) n-1개의 원판을 비어있는 경유지에 옮긴다.  (src -> tran)
2) 남아있는 한개의 원판을 목적지에 옮긴다. (append)
3) 경유지에 있는 n-1개의 원판을 목적지로 옮긴다. (tran -> dst)

이걸 재귀로 구현해주면 된다!