백준 11729, 1914 하노이 탑

과정

https://velog.io/@younghoondoodoom/%EB%B0%B1%EC%A4%80-11729-%ED%95%98%EB%85%B8%EC%9D%B4-%ED%83%91-%EC%9D%B4%EB%8F%99-%EC%88%9C%EC%84%9C
참고했습니다.

• 1번 자리에서 3번자리로 n개의 하노이 탑을 옮겨야 한다면

  1. 1번 자리에서 2번 자리로 n-1 개의 하노이 탑을 옮겨야 한다.
  2. 1번 자리에서 3번 자리로 가장 큰 하노이 탑을 옮겨야 한다.
  3. 2번 자리에서 3번 자리로 n-1개의 하노이 탑을 옮겨야 한다.

• n이 1일 때 중단한다.

• 재귀를 풀 때는 중단 조건을 찾고, 전체 과정을 정형화해야 함.

# 11729
N = int(input())

move = []

def hanoi(level, start, mid, end):
    if level == 1:
        move.append((start, end))
        return
    hanoi(level - 1, start, end, mid)
    move.append((start, end))
    hanoi(level - 1, mid, start, end)

hanoi(N, 1, 2, 3)
print(len(move))
for i in move:
    print(*i)

1914

• 20번 초과한 값이 들어오면, 과정이 아닌 실행 횟수만 출력한다.
• 11729 코드를 그대로 사용하면 메모리 초과 발생.
• 실행 횟수만 계산해야한다.
• 하노이탑 개수가 N개일 때, 실행 횟수는 2**N - 1이다.

# 1914
N = int(input())

ans = 0

def hanoi(level, start, mid, end):
    global ans
    ans += 1
    if level == 1:
        print(start, end)
        return
    hanoi(level - 1, start, end, mid)
    print(start, end)
    hanoi(level - 1, mid, start, end)

print(2**N -1)
if N <= 20:
    hanoi(N, 1, 2, 3)