글 읽기 - 이 코드 시간초과가 나는 이유를 도저희 모르겠습니다 ㅠ

qktlf789456 3년 전 0

시간초과가 나는 이유를 도저희 모르겠네요 ㅠ 3시간동안 풀었는데 해결이 안 되네요..

#include <iostream>
#include <algorithm>
#include <math.h>

#define EMPTY -215214
#define MAX 2147483648

using namespace std;


/*
ios_base::sync_with_stdio(0);
cin.tie(0);
*/

//2147483648

long long table[32][32]{ 0, };
char used_table[32][32]{ 0, };

char first[1000]{ 0, };
char second[1000]{ 0, };
int used_size = 0;
int find_result = 0;


long long pow(int a, int b) //a 를 b승
{
	long long remain = 1;
	long long result = a;

	if (b == 0)
		return 1;


	while (b != 1)
	{
		if (b % 2)
		{
			remain *= result;
			result *= result;
		}
		else
			result *= result;

		b /= 2;
	}

	return result * remain;

}


char count_table[32][32]{ 0, };

void dfs(long long target_num, int used_count) //target_num , used_size
{
	if (find_result)
		return;



	if (target_num == 0) // find result
	{
		used_size = used_count;
		find_result = 1;
		return;
	}





	long long tmp, tmp2;
	for (int i = 31; i >= 0 && find_result == 0; i--)
	{
		for (int j = 31; j >= 0 && find_result == 0; j--)
		{
			tmp = table[i][j];
			if (tmp > target_num || tmp == 0)
				continue;

			//배수약수관계체크
			int invalidata = 1;

			for (int a = 0; a < 32 && table[a][j]; a++)
				if (used_table[a][j]) //사용된것이 있을경우
					invalidata = 0;


			if (invalidata == 0)
				continue;

			for (int a = 0; a < 32 && table[i][a]; a++)
				if (used_table[i][a]) //사용된것이 있을경우
					invalidata = 0;

			if (invalidata == 0)
				continue;



			//사용표시
			used_table[i][j] = 1;

			//check the log
			first[used_count] = i;
			second[used_count] = j;

			dfs(target_num - tmp, used_count + 1);


			//사용해제
			used_table[i][j] = 0;


		}
	}



}

int main()
{
	long long result;
	for (int i = 0; i < 32; i++)
	{
		for (int j = 0; j < 32; j++)
		{
			result = pow(2, i) * pow(3, j);
			if (result > MAX)
				break;

			table[i][j] = result;
		}
	}



	int test_case;
	cin >> test_case;


	long long target_num;


	int next = 1;
	while (test_case--)
	{
		cin >> target_num;


		dfs(target_num, 0); //target_num , used_size

		cout << used_size << "\n";
		for (int i = 0; i < used_size; i++)
		{
			cout << (int)first[i] << " " << (int)second[i] << "\n";
		}


		used_size = 0;
		find_result = 0;


	}




	return 0;
}

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

문제

문제

출처

ICPC

이 코드 시간초과가 나는 이유를 도저희 모르겠습니다 ㅠ

qktlf789456 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말