글 읽기 - 왜틀렷을까요 으으아유

mij9929 4년 전 0

최선을 다했지만 왜 틀렸는지 모르겠습니다. ㅠㅠㅠㅠ

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


void TooLargeNumPow(int n, int arr[]) // 2의 21승 이상인 경우
{
	arr[0] = 2;
	int carry = 0; // carry가 1이 되면 자리 올림
	for (int i = 0; i < n - 1; i++)
	{
		if (i == 0)
			arr[i] *= 2;
		for (int j = 0; j < i; j++)
		{
			arr[j] *= 2;
			arr[j] += carry;
			if (arr[j] >= 10) {
				carry = 1;
				arr[j] -= 10;
			}
			else
				carry = 0;
		}
	}

	arr[0] -= 1; // 1을 빼줌

	int start = 99;
	for (int i = 99; i > -1; i--)
	{
		if (arr[start] == 0) //시작부분을 구함
		{
			start--;
			continue;
		}

		cout << arr[i];
	}
}
void Hanoi(int n, int source, int middle, int destination) //전형적인 하노이 알고리즘
{
	if (n == 1)
	{
		cout << source << " " << destination << "\n";
		return;
	}

	Hanoi(n - 1, source, destination, middle);
	cout << source << " " << destination << "\n";
	Hanoi(n - 1, middle, source, destination);

}
int main()
{
    //혹시나 계산이 느려질까봐
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    
    //시작부분
	int arr[100] = { 0 };
	int n;
	cin >> n;
	if (n <= 20) {
		cout << pow(2, n) - 1 << "\n";
		Hanoi(n, 1, 2, 3);
	}
	else {
		TooLargeNumPow(n, arr);
	}

}