[BOJ] 1914번 하노이 탑 (C++)

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

1914번: 하노이 탑

 

#include <iostream>
#include <cmath>
#include <string>
using namespace std;
 
void move(int no, int x, int y){
	if(no > 1)
		move(no - 1, x, 6 - x - y); 
	cout << x << " " << y << '\n';
	if(no > 1)
		move(no - 1, 6 - x - y, y);
}
 
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
    
	int n;
	cin >> n;
	
	string a = to_string(pow(2, n));
	
	int x = a.find('.');     // pow 함수 결과가 실수형이기에 소수점 찾기
	a = a.substr(0, x);      // 소수점 앞자리만 나오게 하기
	a[a.length() - 1] -= 1;  // string a에 대한 마지막 위치의 인덱스 값에 -1
  
	cout << a << '\n';
	
	if(n <= 20)
		move(n, 1, 3);
	return 0;
}

 

하노이 탑에서 원반이 x개일 때 원반 이동 횟수는 2^x - 1이다. 

그런데 20이 넘어가면 int형으로 표현할 수 없기 때문에 문자열을 이용하여 이 문제를 해결했다. 

먼저 2의 n제곱을 문자열로 만든다. pow 함수는 double형이기 때문에 실수가 저장된다. find를 이용하여 소수점을 찾고 substr을 이용하여 소수점 앞자리만 저장되게 한다. 문자열 마지막 인덱스 값에 접근하여 -1을 해준다.