1808. 지희의 고장난 계산기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yC3pqCegDFAUx&categoryId=AV4yC3pqCegDFAUx&categoryType=CODE

SW Expert Academy

 

곱으로 수를 만드는데 한자리 수가 아닌 여러번을 눌러 만들 수 있는 수를 사용해 최소 반복 횟수를 구하는 문제.

단순 DFS로 풀기 어려웠다.

따라서 곱해서 어떤 수를 만드려면 결국 곱해지는 수들은 X의 약수여야 한다. 약수외의 수를 곱해서는 만들 수 없으므로

X의 모든 약수를 구하기로 한다.

이때 1은 곱하는 것이 횟수만 증가시킬 뿐 결과에 달라지는 것이 없으므로 2부터 X까지의 수중에 약수를 구한다.

그리고 약수가 몇자리수인지 계산해서 약수와 , 자릿수를 페어로 벡터에 저장.

자릿수만큼 버튼을 눌러야 하기 때문.

 

그리고 약수의 곱을 이용해 최소 카운트를 구하도록 DFS를 돌리면 되는데 , 시간초과가 발생할 수 있다.

벡터의 가장 끝에 저장된 수는 X에 가까운 약수이고 (2부터 X까지 조사하였다면)

벡터의 가장 끝에서 부터 시작해 곱셈의 DFS를 돌리면 처음부터 시작하는 것보다 빠르다고 판단.

벡터의 현재 위치에서 곱해질 수 있는 다음수는 자신보다 크지 않은 수로 하기로 한다. (같은 수는 가능)

 

마지막으로 예외처리가 필요한데 1은 약수로 취급을 하지 않았기 때문에 X가 1인 경우 1은 약수가 없는 수가 되어 -1을 출력하게 되므로 1인경우는 따로 2를 출력하도록 예외처리 해주면 끝.

 

 

PS) num은 곱의 결과이므로 큰 수가 나올수 있으니 long long 사용

 

 

 

 

 

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

int mina, counta;
int arr[10];
int N, cur;
bool check;

struct Node {
	int num;
	int count;
};

vector<Node>vec;



void DFS(long long num, int pre)
{

	if (num > N)
	{
		return;
	}
	if (num == N)
	{

		counta++;
		check = true;
		if (mina > counta)
		{
			mina = counta;
		}
		counta--;

		return;
	}

	for (int i = pre; i >= 0; i--)
	{
		counta += 1 + vec[i].count;
		DFS(num * vec[i].num, i);
		counta -= 1 + vec[i].count;
	}
}

int main(void)
{

	int tc;
	cin >> tc;

	for (int test_case = 1; test_case <= tc; test_case++)
	{
		for (int i = 0; i < 10; i++)
		{
			cin >> arr[i];
		}
		cin >> N;

		vec.clear();
		mina = 987654321;
		counta = 0;
		cur = 0;
		check = false;

		for (int i = 2; i <= N; i++)
		{
			if (N % i == 0)
			{
				int temp = i;
				bool flag = true;
				int roop = 0;
				while (temp >= 1)
				{
					if (!arr[temp % 10])
					{
						flag = false;
						break;
					}
					temp /= 10;
					roop++;
				}

				if (flag)
				{
					vec.push_back({ i, roop });
				}
			}
		}

		if (N != 1)
		{

			counta += vec[vec.size() - 1].count;
			DFS(vec[vec.size() - 1].num, vec.size() - 1);
			counta -= vec[vec.size() - 1].count;

			if (check)
			{
				cout << "#" << test_case << " " << mina << endl;
			}
			else
			{
				cout << "#" << test_case << " " << -1 << endl;
			}

		}
		else
		{
			cout << "#" << test_case << " " << 2 << endl;
		}






	}




}