[동적계획법] 하노이탑

예제 ) 하노이탑 원반의 개수가 주어질 때 원반을 이동시킬 최소 횟수를 구하시오. 

 

 

규칙

1. 1회에 한 개의 원판만 옮길 수 있다.

2. 반드시 큰 원판 위에 작은 원판이 있어야 한다. 

 

.

 

 

1번에 쌓여있는 원판들을 규칙을 지키며 3번까지 옮겨야 한다. 동적계획법의 TopDown 방식에 따라 결과부터 생각해보자.

 

 

 

 

 

 n개의 원판을 3번 막대로 옮기려면 우선, n-1개 원판을 2번 막대로 옮겨야 한다. 

 

 

 

 

 

그래야 가장 큰 원판을 3번으로 옮길 수 있다. 

 

 

 

 

 

 

그 다음, 2번 막대의 n-1개 원판을 다시 3번 막대로 옮긴다. 

 

---

 

공식으로 나타내보자. 

 

n : 원판 갯수

F(n) : n개의 원판을 한 막대에서 다른 막대로 옮기는 경우의 최소 횟수

 

과정

1) n-1개 원판을 1번에서 3번으로 이동 : F(n-1) 

2) 가장 큰 원판 1번에서 3번으로 이동 : 1

3) n-1개 원판을 2번에서 3번으로 이동 : F(n-1)

 

F(n) = 2F(n-1) + 1

 

공식이 나왔으니 BottomUp 방식으로 하나씩 구해보자. 

 

F(0) = 0가지

F(1) = 2*0 + 1 = 1가지

F(2) = 2*1 + 1 = 3가지 

F(3) = 2*3 + 1 = 7가지

F(4) = 2*4 + 1 = 9가지

.

.

.

 

---

 

 

참고자료

2021년 7기 모집대비 SSAFY(삼성 청년 SW아카데미) SW적성진단 5일 완성