## 문제

하노이의 탑 구현

원판의 수 N이 첫 줄에 주어진다

N이 20 이하일 경우 이동과정도 출력


## 풀이

'''
def hanoi(from_n,to_n,n):
    # l1의 n개를 l3으로 옮기는 과정
    l1 = [i for i in range(n,0,-1)]
    l2 = []
    l3 = []
    count = 0

    # 1. 옮길 방향으로 가장 작은 것을 이동
    # 2. 다른곳에 2 이동
    # 3. 크기 1을 크기 2 위로
    # 4. 크기 3 이동
    # 5. 크기 3 있던 자리에 크기 1 놓고, 크기 2를 크기 3 위로, 크기 1을 크기 2 위로

    # 가장 작은것의 크기는 n-2
    # 중간크기 n-1, 가장 큰것 n
    print(l1,l2,l3)
    #1
    l1.pop()
    l3.append(1)
    print(l1,l2,l3)
    #2
    l1.pop()
    l2.append(2)
    print(l1,l2,l3)
    #3
    l3.pop()
    l2.append(1)
    print(l1,l2,l3)
    #4
    l1.pop()
    l3.append(3)
    print(l1,l2,l3)
    #5
    l2.pop()
    l1.append(1)
    print(l1,l2,l3)
    #6
    l2.pop()
    l3.append(2)
    print(l1,l2,l3)
    #7
    l1.pop()
    l3.append(1)
    print(l1,l2,l3)

    return count'''

# hanoi(3,A,C,B) 3개를 c로 옮기기 위해서는
#   hanoi(2,A,B,C) 위의 2개를 B로 옮기고
#   hanoi(1,A,C) 하나를 c로 옮기고
#   hanoi(2,B,C,A) 다시 2개를 c로 옮기면 된다


## 코드

```python

def hanoi(n,from_n,to_n,via_n,isprint,c):
    if n==1:
        c += 1
        if isprint:
            print(from_n,to_n)
            return c
    hanoi(n-1,from_n,via_n,to_n,isprint,c)
    hanoi(1,from_n,to_n,via_n,isprint,c)
    hanoi(n-1,via_n,to_n,from_n,isprint,c)
    return c

def main():
    n = int(input())
    c = 0
    if n<=20: isprint=True
    print(hanoi(n,1,3,2,isprint,c))
    return None

main()

```

그냥 코드부터 짜기엔 어렵고, from, to 정보만 있으면 될거라고 생각했는데 코드 구현할때는 경유하는 via까지 받아오는게 편한걸로 보인다.

타워 1,2,3(스택)을 직접 만들지 않아도 된다. 이동했다고 표시만 하면 개념적으로 구현이 된 거라고 볼수 있을것 같다. 어떤 타워에서 어디로 이동했는지 출력하는데 문제가 없다.

1. count는 어디에?

2. 출력은 count 뒤에 나와야 한다.


def hanoi(n,from_n,to_n,via_n,mv):
    if n==1:
        mv += [[from_n,to_n]]
        return mv
    hanoi(n-1,from_n,via_n,to_n,mv)
    hanoi(1,from_n,to_n,via_n,mv)
    hanoi(n-1,via_n,to_n,from_n,mv)
    return mv

def main():
    n = int(input())
    mv =[]
    mv = hanoi(n,1,3,2,mv)
   
    print(len(mv))
    if n<=20:
        for tmp in mv:
            print(*tmp)
    return None

main()

직접 셀 필요가 없고 이동과정을 가지고 나와서 길이를 재면 될거라고 생각했는데 메모리 초과 된다.


def hanoi(n,from_n,to_n,via_n):
    if n==1:
        print(from_n,to_n)
        return None
    hanoi(n-1,from_n,via_n,to_n)
    hanoi(1,from_n,to_n,via_n)
    hanoi(n-1,via_n,to_n,from_n)
    return None

def main():
    n = int(input())
    print(2**n-1) # 하노이탑의 이동횟수
    if n <= 20:
        hanoi(n,1,3,2)
    return None

main()

원판수가 20이 넘을경우 이동횟수만 공식으로 출력되도록 했다


def h(n,a,b,c):
    if not n:
        return
    h(n-1,a,c,b)
    print(a,b)
    h(n-1,c,b,a)

num=int(input())
print(2**num-1)
if(num<=20):
    h(num, 1, 3, 2)

다른사람 풀이