11729번 : 하노이 탑 이동 순서

이동 횟수는 dp로, 이동 순서는 재귀적으로 짜보았습니다.

우선 이동 횟수부터.

원판이 1개 있을 때의 이동 횟수는 1

원판이 2개 있을 때의 이동 횟수는 3

원판이 3개 있을 때의 이동 횟수는 7

원판이 4개 있을 때의 이동 횟수는 15

...

이것은 원판 N개가 1번에서 3번으로 이동할 때

1) N-1개가 1번에서 2번으로 이동 / 이동 횟수 : dp[N-1]

2) 가장 아래에 있던 원판이 1번에서 3번으로 이동 / 이동 횟수 : 1

3) 2번에 옮긴 모든 원판을 다시 2번에서 3번으로 이동 / 이동 횟수 : dp[N-1]

이런 순서로 됩니다.

이동 횟수를 모두 세어보면 결국 2*dp[n-1]+1번이 됩니다.

(사실 dp를 안세워도 이동 횟수는 2의 n제곱-1번과 같습니다)

이제 이동 순서를 구해보겠습니다.

원판을 이동시킬 때는 다음과 같은 규칙이 발생합니다.

"N개를 a번에서 b번으로 (이때 남은 번호는 left) 이동하는 것은 N-1개를 a에서 left로 이동시키고 남은 1개를 a에서 b로 이동시키고, 이동시킨 N-1개를 left에서 b번으로 이동시킨 것과 같다."

즉 이동하는 함수가 f(int N, int a, int b, int left)라고 할 때

f(n - 1, a, left, b);

f(1, a, b, left);

f(n - 1, left, b, a);

와 같다는 거죠.

출력은 전달받은 N이 1일 때 a와 b를 순서대로 출력해주면 됩니다.

#include <stdio.h>

int dp[21];

int cnt=0;

int arr[3][20];

void f(int n, int a, int b, int left){

if (n == 1){

printf("%d %d\n", a, b);

cnt++;

}

else{

f(n - 1, a, left, b);

f(1, a, b, left);

f(n - 1, left, b, a);

}

}

int main(){

int N;

scanf("%d", &N);

dp[1] = 1;

for (int i = 2; i <= N; ++i){

dp[i] = dp[i - 1] * 2 + 1;

}

printf("%d\n", dp[N]);

f(N, 1, 3, 2);

}