[백준 11729] 하노이 탑 이동 순서

www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

하노이 탑의 규칙성을 찾으면 금방 풀 수 있는 문제이다 

(과거에 수업에서 이문제를 배운 기억이 있었지만 다 까먹어서 생각하는데 애를 좀 먹었다..ㅎㅎ)

 

규칙을 설명드리면 다음과 같아 

예시) 4인 경우 

 

1

2

3

4

----------

a   b   c

 

1위의 모든 블록을 3으로 옮길때 

이를 나눠서 생각하면 4개의 블록을 옮기는 테스크를 크게 3개로 나눠볼수 있다 

 

 

1

2

3

----------

a   b   c  

 

a위에 모든 블록(1,2,3)을  1 > 2로 옮기기 

---

     1

     2

4   3

----------

a   b   c   

 

a위에 블록 4를 1 > 3 로 옮기기

---

     1

     2

     3   4

----------

a   b   c   

 

a위에 모든 블록(1,2,3)을  2 > 3로 옮기기 

 

 

위와 같이 문제를 3가지로 나눠서 풀면 쉽게 풀린다.

 

맨 처음으로 출력해야하는 값 또한 위 규칙을 적용해서 풀면

 

n 블록의 최소 이동 횟수 는

n = (n-1)*2 + 1        이다.

 

또하나 명심할것은 print가 많은 테스크에서 printf 와 cout에 속도차이를 실감하게 될것이다. 

처음에는 cout으로 했을때 시간초과가 났는데 이를 printf로 고치니까 바로 통과...했다 ㅎㅎ..

(사실 함수돌아가는 방식만 이해해도 그럴거같은게 printf와 같은 함수는 서식문자를 통해 표현할 자료형을 명시해주는 반면 cout 같은

경우에는 자료형을 명시하지않고 함수자체가 찾아서하는 느낌이 강하다 = 과연 어느게 컴퓨터입장에서 빠르게 이해하기 쉬운 테스크로 보이는가?)

 

 

 

코드는 다음과 같다.

 

 

#include <iostream>
#include <stdio.h>

using namespace std;

void Hanoi(int N,int nSrc, int nTar, int nOth)
{
    if(N == 1)
    {
        printf("%d %d\n", nSrc, nTar);       
    }
    else
    {
        Hanoi(N-1,nSrc, nOth, nTar);
        printf("%d %d\n", nSrc, nTar);       
        Hanoi(N-1, nOth, nTar, nSrc);
    }
}


int main(void)
{
    int N = 0;
    int nCnt = 1;
    cin >> N;

    
    for(int i = 2; i <= N; i++)
    {
        nCnt = 2*nCnt + 1;
    }

    printf("%d\n", nCnt);    

    Hanoi(N, 1, 3, 2);
    
    return 0;
}