[백준/c++] 11729번 - 하노이 탑 이동 순서

문제

11729번: 하노이 탑 이동 순서

풀이

분류 : 분할 정복

 

주어진 예제로 하노이의 탑 원리를 생각해봅니다.

 

(1)원판의 갯수가 1개일 경우

-하나뿐이므로 3번기둥으로 바로 옮깁니다.

1 3

 

(2)원판의 갯수가 2개일 경우

-1. 먼저 원판 1개를 2번기둥으로 이동. 1번기둥엔 제일 큰 원판 하나만 남게 됩니다.

1 2

-2. 1번기둥의 원판을 3번기둥으로 옮깁니다.

1 3

-3. 2번기둥의 원판을 3번기둥으로 옮깁니다.

2 3

 

(3)원판의 갯수가 3개일 경우

-1. (2)의 방식대로, 먼저 원판 2개를 2번기둥으로 이동. 1번기둥엔 제일 큰 원판 하나만 남게 됩니다.

1 3
1 2
3 2

-2. 1번기둥의 원판을 3번기둥으로 옮깁니다.
1 3

-3. 2번기둥의 원판을 3번기둥으로 옮깁니다.

2 1
2 3
1 3

 

이를 통해서

1. 1번기둥의 n-1개를 2번기둥으로 이동. 1번기둥엔 제일 큰 원판 하나만 남음.

2. 1번기둥의 제일 큰 원판을 3번기둥으로 이동.

3. 2번기둥의 n-1개의 원판을 모두 3번기둥으로 이동.

 

와 같은 규칙으로 진행됨을 알 수 있습니다.

또한 이동횟수는 1개 : 1, 2개 : 3, 3개 : 7 . . . n개 : (2^n)-1 임을 알 수 있습니다. 

 

코드(O(n^2)) *O(n^2)가 아니라면 알려주세요. 감사합니다(--)(__)*

*제곱값을 구해주는 #include<cmath>의 pow()를 쓰면 오답인 이유 :

c++11기준 pow()의 원형함수입니다.

 

double pow (double base     , double exponent);  float pow (float base      , float exponent);  long double pow (long double base, long double exponent);  double pow (Type1 base      , Type2 exponent);        // additional overloads

리턴타입이 double, float, long double, double이므로, pow()는 사실 실수형으로(!) 계산되기 때문에 pow(2,n)-1로 작성하면 오답이 나오게 됩니다.

자세한 사항은 아래의 레퍼런스 사이트를 참고해주세요.

pow - C++ Reference