문제55
-
문제55. 공포의 하노이의 탑🧠 codingtest/javascript 100제 2022. 3. 31. 09:15
하노이의 탑은 A,B,C 3개의 기둥과 기둥에 꽂을 수 있는 N개의 원판으로 이루어져 있음 다음의 규칙을 만족해야함 처음의 모든 원판은 A 기둥에 꽂혀 있다 모든 원판의 지름은 다르다. 이 원반은 세 개의 기둥중 하나에 반드시 꽂혀야 한다. 작은 원반 위에 큰 원반을 놓을 수 없다. 한 번에 하나의 원판(가장 위에 있는 원판)만을 옮길 수 있다. A 기둥의 원반 N개를 모두 C원반으로 옮기고 싶다. 모든원반을 옮기기 위해 실행되어야할 최소 원반 이동 횟수를 계산하여라. 미리 생각해 봐야할 것 원반 갯수(n)에 따른 이동 횟수 n = 1, 1번 n = 2, 3번 n = 3, 7번 n = 5, 15번 다음과 같은 점화식을 가진다 2^n - 1 = 이동횟수 그렇다면 이동경로는 어떻게 추적할수 있을까? 위와 같..