글 읽기 - 시간초과 원인을 모르겠습니다.

suhwanpark 4년 전 0

어떤걸 수정해야할지 모르겠습니다.

혹시 아시는분 조언 부탁드립니다~!!

#include <iostream>
#include <string>


using namespace std;

void hanoi_tower(int N, int from, int tmp, int to) 
{
	if (N <= 20) {
		if (N == 1) 
		{
			cout << from << " " << to << endl;
		}
		else {
			hanoi_tower(N - 1, from, to, tmp);
			cout << from << " " << to << endl;
			hanoi_tower(N - 1, tmp, from, to);
		}
	}
}

int pow(int N)
{
	int result=1;
	for (int i = 0; i < N; i++)
	{
		result *= 2;
	}
	return result;
}

string bigNumAdd(string num1, string num2)
{
	long long sum = 0;
	string result;
	string _result;
	//1의 자리부터 더하기 시작한다
	while (!num1.empty() || !num2.empty() || sum)
	{
		if (!num1.empty())
		{
			sum += num1.back() - '0';
			num1.pop_back();
		}
		if (!num2.empty())
		{
			sum += num2.back() - '0';
			num2.pop_back();
		}
		//다시 string 형태로 만들어 push_back
		result.push_back((sum % 10) + '0');
		sum /= 10;
	}

	for (int i = 0; i < result.length(); i++)
	{
		char temp;
		temp = result[result.length()-i-1];
		_result.push_back(temp);
	}
	return _result;
}

//2의 n승은 0으로 끝날 수 없으므로
string subtractOne(string num)
{
	int back = num.back() - '0';
	num.pop_back();
	back -= 1;
	num.push_back(back + '0');

	return num;
}

int main() {

	iostream::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;

	if (n <= 20) 
	{		
		cout << pow(n)-1 << endl;
		hanoi_tower(n, 1, 2, 3);		
	}
	else
	{		
		string num = "2";
		for (int i = 0; i < n - 1; i++)
		{
			string temp = bigNumAdd(num, num);
			num = temp;
		}
		cout << subtractOne(num) << endl;	
	}

	return 0;
}

djm03178 4년 전 2

endl만 '\n'으로 바꾸면 됩니다.

haptic12 4년 전 0

정말 대단하네요. 처음 겪었습니다. 저도 이것으로 해결하였습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 원인을 모르겠습니다.

suhwanpark 4년 전 0

djm03178 4년 전 2

haptic12 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말