[백준 C++] 1914 하노이 탑

https://www.acmicpc.net/problem/1914

1914번: 하노이 탑

가장 기본적이게 보이는 하노이 탑 문제이다. 

 

우선 내가 이문제를 해결할 방식은 다음과 같다.

N층의 하노이 탑을 N-1층의 하노이탑 문제를 해결할 수 있도록 함. 즉 재귀로 구현할 수 있을 것이다.

이런 과정을 거치면 우선 N층의 이동 횟수는 ( N-1층 이동 횟수 ) * 2 + 1 이다. 

 

위 내용들을 바탕으로 코드 구현 ( ** 정답 아님 ** )

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n;
ll mov_cnt[110];

void mov(ll cnt, ll from, ll path, ll to) {

	if (cnt == 1) {
		cout << from << ' ' << to << '\n';
		return;
	}

	mov(cnt - 1, from, to, path);
	cout << from << ' ' << to << '\n';
	mov(cnt - 1, path, from, to);
}


int main(void) {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;

	mov_cnt[1] = 1;
	for (ll i = 2; i <= n; i++) {
		mov_cnt[i] = mov_cnt[i - 1] * 2 + 1;
	}
	cout << mov_cnt[n] << '\n';

	if(n <= 20) mov(n, 1, 2, 3);

}

그냥 점화식이 나왔으므로 DP처럼 구현했다.

하지만... 이렇게 되면 큰 수를 다룰 수가 없다... 

점화식 자체가 매우 간단하며 무려 초기값이 1이라서 계속 실행하면 N층의 하노이 탑의 이동 횟수는 2^n -1이라고 볼 수 있다.

 

또한 우리는 큰 수, 무려 2의 100승!을 봐야하므로 숫자로 다루기엔 무리가 있다고 판단. string으로 다뤘다.

string형태로 저장한 후에 pow의 반환값이 float이므로 소수점 나오는건 지워주고, -1까지 수행해주면 된다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n;

void mov(ll cnt, ll from, ll path, ll to) {

	if (cnt == 1) {
		cout << from << ' ' << to << '\n';
		return;
	}

	mov(cnt - 1, from, to, path);
	cout << from << ' ' << to << '\n';
	mov(cnt - 1, path, from, to);
}


int main(void) {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;

	string s = to_string(pow(2, n));
	ll idx = s.find('.');
	s = s.substr(0, idx);
	s[s.length() - 1] -= 1;
	cout << s << '\n';

	if(n <= 20) mov(n, 1, 2, 3);

}