1808. 지희의 고장난 계산기

1808. 지희의 고장난 계산기

처음에 BFS로 풀려했지만, 뭔가 실마리가 보이지 않아 그냥 완전탐색을 했다.

근데 완전탐색도 어떤식으로 할까 고민하다가, 계산기에 곱하기 밖에 없다는 점을 알고 문제를 풀었다.

곱하기이기 때문에, 주어진 N의 약수들을 모두 구했다. 그리고 그 약수들 중에서 주어진 값으로 만들 수 있는 것만

canmake 벡터에 담아주었다, 그 길이와 함께.

그리고 canmake 안의 값들을 재귀로 모든 값을 구하도록 하였다.

수를 만드는 과정에서 int 변수를 넘어가서, 오류 나는게 있어서 long long 타입으로 바꿔주었고,

가지치기를 위해서 큰수부터 하면서, 이전 값을 저장해서 계속해서 큰수가 만들어지지 않도록 pre 라는 변수를 넘기면서 재귀를 구현했다.

또 0과 1일때는 따로 답을 구하도록 하였다.

1이면 재귀에서 1을 계속 곱하면 답이 나오지 않기 때문에, 그리고 0은 약수가 없으므로..

<정답 코드>

#include<iostream>
#include<vector>
using namespace std;
int n;
int have[10];
long long ans;
vector<pair<int, int>> canmake;
const int INF = 987654321;
 
void go(int k,long long cmp, int pre)
{
    if (cmp > n)
    {
        return;
    }
    if (cmp == n)
    {
        if (k < ans)
        {
            ans = k;
        }
 
        return;
    }
 
    for (int i = pre; i>=0; i--)
    {
        if (canmake[i].first != 1)
        {
            go(k + canmake[i].second + 1, cmp*canmake[i].first , i);
        }
        
    }
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
 
    for(int t=1;t<=tc;t++)
    {
        canmake.clear();
        ans = INF;
 
        for (int i = 0; i < 10; i++)
        {
            cin >> have[i];
        }
 
        cin >> n;
 
        for (int i = 1; i <= n; i++)
        {
            if (n%i == 0)
            {
                int r = i;
                int len = 0;
                bool chk = true;
 
                while (r!=0)
                {
                    len++;
                    if (have[r % 10])
                    {
                        r /= 10;
                    }
                    else
                    {
                        chk = false;
                        break;
                    }
                }
 
                if (chk)
                {
                    canmake.push_back({ i,len});
                }
            }
        }
 
        if (n == 0)
        {
            if (have[0])
            {
                ans = 2;
            }
            else
            {
                ans = -1;
            }
        }
        else if (n == 1)
        {
            if (have[1])
            {
                ans = 2;
            }
            else
            {
                ans = -1;
            }
        }
        else
        {
            go(0, 1, canmake.size()-1);
        }
    
        if (ans == INF)
        {
            ans = -1;
        }
 
        cout << "#" << t << " "<<ans<<"\n";
    }
    
 
    return 0;
}