[Baekjoon/백준] 11729번 Python

문제 출처: www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

1. 문제 접근 방식

- 먼저, 하노이탑의 동작 방식을 파악하는 것이 중요하다. 첫번째 단계는 가장 밑의 판을 제외한 나머지를 중간으로 옮기고 가장 밑의 판은 마지막으로 옮긴다. 마지막으로 가운데에 있는 판들을 마지막으로 옮겨주면 끝이 난다.

 

2. 내가 푼 코드

import sys

N = int(sys.stdin.readline())

# n개의 원판이 있을 경우 가장 밑의 원판을 제외한 나머지를 b로 옮김
# 가장 밑의 원판을 c로 옮기고 b로 옮겨뒀던 나머지들을 다시 c로 옮김


def hanoi(n, a, b, c):
    if n == 1:
        print(a, c)
    else:
        hanoi(n-1, a, c, b)
        print(a, c)
        hanoi(n-1, b, a, c)


cnt = 0

for i in range(N):
    cnt = cnt * 2 + 1

print(cnt)
hanoi(N, 1, 2, 3)

3. 결과 및 느낀점

- 성공! 재귀의 가장 기본인 문제였다. 재귀 마스터를 위해 더 열심히 해야겠다.