11729번 하노이 탑 이동 순서(재귀, pow, 입출력) - ☆

#문제링크 : https://www.acmicpc.net/problem/11729

<전략>

1. 대표적인 분할정복 문제로, 하나의 원판은 1->3으로 하면 된다. 두개의 원판은 맨 밑에 원판을 제외한 바로 위 원판 하나를 2로 옮기고 맨 밑에 있던 원판을 3으로 옮긴뒤, 다시 2에 있던 원판을 3으로 옮기면 된다. 그렇다면 3개, 4개, 100개는 어떻게 옮길까?

2. n개의 원판을 1, 2, 3 장대를 이용해서 옮기는 문제는 n번째 원판을 제외한 n-1개의 원판을 1에서 3을 통해 2로 전부 옮긴 후에, n번째 원판을 1에서 3으로 옮긴다. 그리고 2에 있던 n-1개의 원판들을 1을 통해 3으로 옮기면 해결할 수 있다.

※주의사항

1. 원판의 갯수와 시작점, 경유점, 도착점을 지정해주어야 하기 때문에, 4개의 파라미터가 필요하다.

2. pow함수는 결과값이 100만이 넘어가면 지수표기법으로 출력하기 때문에 위험하다. 따라서 (1<<n)과 같이 쉬프트 연산을 통해 2의 N제곱을 표현해준다. (이진수이기 때문에 2의 제곱배가 되는것.)

3. cin과 cout, scanf와 printf는 섞어 쓰지 말자. 그리고 되도록이면 scanf와 printf를 쓰도록 하자.

Code