꾸준하게 거북이처럼

1914번: 하노이 탑 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 어제도 하노이 탑 문제(11729번)를 풀었는데, 오늘은 문제에서의 조건이 조금만 다른 하노이 탑 문제를 리뷰한다. 이 문제에서는 20이하의 입력일 때는 옮긴 횟수와 그 과정까지 출력이지만, 20을 넘어서면(20< n 즉 2^n - 1 이 점화식임을 알 수 있다. 심각하게 생각하지말고 센스를 길러보자^^ 참고: https://bgspro.tistory.com/6

하노이 탑은 정말 유명한 대표적인 재귀 알고리즘 문제이다. 그렇기 때문이기도 하고 전에 배웠지만 또 까먹어서 정확히 개념을 정리하고자 한다. 하노이 탑에서는 결국은 목적이 모든 원반을 하나씩 옮겨서 1에서 3으로 다 옮겨야한다. 그렇다면 이를 반복적인 부분을 고려해서 크게 3가지로 세분화 할 수 있는데, 1. 작은 원반 n-1개를 즉, 맨 아래 원반을 제외한 나머지 원반. 을 A 에서 B로 이동 2. 큰 원반인 제일 아래 원반 1개를 A에서 C로 이동 3. 작은 원반 n-1개를 다시 B에서 C로 이동 이렇게 크게 나눌 수 있다. 재귀니까 종료조건도 생각해야하는데 n-1부분 재귀를 하다보면 1개가 남을 것이다. 그 때가 종료 조건이 된다. 파이썬 코드로 옮겨 보자면 n = int(input()) a = [..