boj 하노이탑 두가지 문제중 n=100인 경우를 출력하는 문제를 c++로 하결하는 경우.

 

+++++++++++++++++++23.4.9

int로 표현할 수 있는 경우. 21억

long long 으로 표현할 수 있는 경우. 922경

unsigned long long 으로 표현할 수 있는 경우 922경 *2

일단 하노이탑 100번째를 구하기 위해서 어떤식으로 해야할지에 대해서 고민중이고, 

그 과정에서 그동안 조금 헷갈리던 인트, 롱롱 , 언사인드 등으로 나타낼 수 있는 숫자의 범위에 대해서 알게되어서 이렇게 기록해둔다. 

조금 더 고민해보다가 일단은 함수구현부터 하도록 하고, 하노이탑의 경우처럼 100번째를 연산하려면 어떤식으로 해야할지에 대해서는 검색해보아야 할것 같다. 

 

+++++++++++++++++++23.4.10

일단 boj에 내가 접한 하노이 탑 문제가 두가지 있는데, 11729번 문제, 그리고 1914번 문제, 이렇게 두가지를 접해보았다. 

그동안 내가 1914번 문제를 접하고, 이거 과거에 풀어봤던 하노이탑 문제인데, 과거에 과연 n=100인 경우까지 어떻게 해결했을까, c++의 경우 long long int가 2^63 -1 인 922경까지 표시하고, 그리고 unsigned로 했을경우 마이너스 영역의 범위까지 플러스로 쭉 밀어서 922*2 경을 표시할 수 있었는데, 그렇기때문에 이렇게 해서 문제를 해결하려고 하더라도 2^64-1 범위까지 밖에 표현이 안되서, 1914번의 경우 2^100-1인 경우를 표시해야 하는데 어떻게 하더라 하고 고민을 많이 했는데, 찾아보니까 과거에 내가 풀었던 문제는 11729번 문제여서 범위가 20까지였고, 1914번 문제의 경우 범위를 n=100까지 늘린 문제로 과거에 풀어보지 못한 문제였다. 

 이 문제를 통해서 생각해 볼 수 있는 문제는 과연 unsigned long long의 범위를 벗어나는 수준에서의 수를 c++에서는 어떤식으로 표현해야 할지에 대해서였다. 

 먼저 정글과정에서 다른 팀원들은 모두 파이썬을 활용하여서 문제를 해결하는데, 파이썬은 초기에 변수를 설정할때 제약없이 그냥 변수명으로 시작해서 알아서 값이 잘 나왔다. 그런 부분에서는 범위가 아주 커다란 답을 가지고 있는 문제의 경우 파이썬으로 해결하는것이 더욱 간결할 수 있겠다는 생각이 든다. 

 

그리고 c++로 문제를 해결해야 하는데, unsigned long long의 범위를 벗어나는 수준에서의 수는 string으로 변수타입을 잡아서 해결해주어야 한다는걸 알 수 있었다. 

 

여러 사람들이 작성한 코드들을 보았는데, 그중에서 가장 전체적인 형태가 이해되고, 공부하기 좋은 코드를 발견하여서 여기에 첨부하고 발견하게 된 블로그 주소를 첨부한다. 

지속적으로 읽어보면서 c++에서 큰 수를 string으로 표현하는 방법에 대해서 알아보자. 

만약 문제를 풀때 c++ unsigned long long int의 범위를 벗어나는 답을 내야하는 문제를 만난다면, 다음에는 파이썬을 이용하는걸 생각하는것이 더 빠르고 편할것 같다. 

파이썬으로 문제를 해결하는것이 익숙해지면 그렇게 해보도록 하자. 

 

#include <cmath>
#include <string>
#include <iostream>

using namespace std;

void hanoi(int n, int start, int mid, int end) {
	if (n == 0) {
		return;
	}

	hanoi(n - 1, start, end, mid);
	cout << start << ' ' << end << '\n';
	hanoi(n - 1, mid, start, end);
}

string bigsum(string s1, string s2) {
	int carry = 0;
	string ans = "";
	for (int i = s1.size() - 1; i >= 0; i--) {
		int sum = s1[i] - '0' + s2[i] - '0' + carry;
		carry = sum / 10;
		string tmp = to_string(sum % 10);
		ans = tmp + ans;
	}
	if (carry) {
		ans = '1' + ans;
	}
	return ans;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n; cin >> n;
	if (n <= 20) {
		cout << (int)pow(2, n) - 1 << '\n';
		hanoi(n, 1, 2, 3);
	}
	else {
		string tmp = "2";
		for (int i = 0; i < n - 1; i++) {
			string ans = bigsum(tmp, tmp);
			tmp = ans;
		}
		tmp[tmp.size() - 1] -= 1;
		cout << tmp << '\n';
	}

	return 0;
}

https://noel-embedded.tistory.com/702

1914 하노이 탑