[BOJ] 하노이 탑_1914 C++ 풀이

문제

n개의 원판을 두 가지 조건에 따라 1번 탑에서 3번 탑으로 전부 이동 시키는데 이동한 최소 회수를 출력하는 문제이다.

1. 한번에 한개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

접근 방법

n이 작은 경우 부터 생각해 보았다.

• n=1인 경우, TOH$($1, a, b, c) 1,2,3번 탑을 각각 a,b,c라고 하면 간단히 (from) a 의 원판을 (to) c로 옮겨 주면 된다. 실제로 원판을 a에서 c로 옮기는데 b를 사용하진 않았지만 함수 작성을 위해 (using) b를 사용했다고 쳤다.

1. from ‘a’ to ‘c’ using ‘b’

• n=2인 경우, TOH$($2, a, b, c)

  1. from ‘a’ to ‘b’ using ‘c’ => TOH$($1, a, c, b);
     
  2. from ‘a’ to ‘c’ using ‘b’
     
  3. from ‘b’ to ‘c’ using ‘a’ => TOH$($1, b, a, c);

• n=3인 경우, TOH$($3, a, b, c)

  위의 n=2인 경우를 사용하면 원판을 한번에 2개 옮길 수 있다.

  1. TOH$($2, a, c, b);
  2. from ‘a’ to ‘c’ using ‘b’
  3. TOH$($2, b, a, c);

즉, 원판의 개수가 n이라면 n-1개의 원판을 옮긴 과정을 사용하여 a의 n-1개의 원판을 b로 옮겨 놓고 가장 큰 원판 1개를 a에서 c로 옮긴 후 나머지 b의 원판들을 c로 옮겨주면 되는, 재귀를 이용하면 되겠다는 생각을 할 수 있었다.

단, n의 값이 조금만 커져도 이동 횟수를 unsined long long으로도 표현할 수 없었기 때문에 string을 써서 이동 횟수를 표현 해야 했다. n=1,2,3일때의 이동 회수를 통해 n개의 원판의 이동 횟수는 2ⁿ-1인걸 알 수 있었다.

to_string, find, substr등의 string 클래스를 처음 사용해 보았고 to_string으로 정수를 문자열로 변경 하였을때 소수점 아래 수 까지 반환 된다는 것을 알게 되었다.

구현

#include<iostream>
#include<string>
#include<cmath>
using namespace std;

void TOH(int n, int a, int b, int c)
{
    if(n>0)
    {
        TOH(n-1, a, c, b);
        cout<<a<<' '<<c<<'\n';
        TOH(n-1, b, a, c);
    }
}

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, c;

    cin>>n;
    if(n<=20)
    {
        c=pow(2,n)-1;
        cout<<c<<'\n';
        TOH(n, 1, 2, 3);
    }
    else
    {
        string s = to_string(pow(2,n));
        int idx=s.find('.'); // 소수점 없에기 위해
        s=s.substr(0,idx); // 소수점 없에기 위해
        s[s.length()-1]-=1;
        cout<<s<<'\n';
    }
    return 0;
}

BOJ_하노이 탑