반응형
https://www.acmicpc.net/problem/11729
11729번: 하노이 탑 이동 순서
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로
www.acmicpc.net
n = int(input())
def recursion(num, cur, next):
if num == 1:
print(cur, next)
return
recursion(num-1, cur, 6-cur-next)
print(cur, next)
recursion(num-1, 6-cur-next, next)
print(pow(2, n)-1)
recursion(n, 1, 3)지금 이 문제와 이전 별찍기 문제를 풀어보면서 느낀 건, 재귀에 좀 약한 것 같다. 연습이 많이 필요하다.
재귀 문제를 풀 때 순간 뇌정지가 온다. 막상 영감이 떠오르면 금방 푸는데도 말이다.
특히나 재귀의 well-known 주제인 하노이탑을 모르면 안된다.
n층의 하노이 탑이 있다고 해보자.
가장 밑에 있는 n번째 원판을 현재위치(cur)에서 원하는 위치(next)로 옮기려면,
1~n-1번째가 쌓아져있는 원판 묶음을 임시위치(6-cur-next)로 옮기고,
n번째 원판을 원하는 위치(next)로 옮기고,
다시 원판 묶음을 임시위치에서 원하는 위치(next)에 옮겨야 한다.
이 과정에서 1~n-1번째 원판 묶음을 임시 위치로 옮길 때에는
다시 1~n-2번째 원판 묶음부터 .... 이런 식으로 재귀적으로 움직인다.
댓글