[BJ] 11729 - 하노이 탑 이동 순서 (재귀)

 

 

재귀를 안쓰다가 이걸 풀려니까 기억이 안났다

 

하노이탑의 규칙은 1,2,3번 기둥이 있고 N개의 원판들이 1번원판에 모두 꽃혀있다 이 N개의 원판을 3번 기둥에

모두 꽃으면 되는데 큰 원판은 작은원판 위에 올 수 없다.

 

옮긴 횟수 K를 구하려면

N개의 원반이 있으면 1번부터 N-1번 원반까지 모두 2번쨰 기둥에 들어가야한다.

N번 원반이 3번기둥에 한번 이동하고 1 ~ N-1번 원반이 2번기둥에서 N번원반이 올려져있는

3번기둥으로 이동해야하니 총 이동 횟수는 f(n) = 1 + 2f(n-1)이 된다 즉 (2^n) - 1 번 이동을 하게 된다.

 

즉

N-1개의 원판을 기둥 1에서 기둥 2로 옮긴다

N번 원판을 기둥 1에서 기둥 3으로 옮긴다

N-1개의 원판을 기둥 2에서 기둥 3으로 옮긴다

-> 원판이 n-1개일떄 옮길 수 있으면 원판이 n개일 떄에도 옮길수 있다.

 

-> 원판이 1개일떄 원판을 내가 원하는 곳으로 옮길 수 있다.

원판이 K개일 떄 옮길 수 있으면 원판이 K+1개일 떄에도 옮길 수 있다.

귀납적 사고

 

cout << (1 << k) -1 이 이해가 안간다면

이동횟수가 (2^n) - 1번인건 알고있을거라 생각하고

1은 2진수로 0001이다 이걸 LeftShif연산자로 밀게되면 0010이 나온다

0010은 2다

즉 K가 3이라 치면

0001 을 3번 왼쪽으로 이동시켜라 즉

1000 이 나오게되고 즉 8이 된다.

 

그래도 하노이 탑이 이해가 안간다면

https://www.youtube.com/watch?v=vq7dpFWpwAE

해당 영상을 참고하도록 하자.