lv3 N으로 표현.

버섯수 앞서는 생각이 필요하다.

 

첫 생각 :

 

d[32001] 을 해줘서.

 

d[0] 부터 시작한다.

 

n은 0 초과 32000 이하를 지켜주면서

=> n+5  n+55 n+555 n+5555 ......

     n-5   n-55  n-555 n-5555 ......

    n*5    n*55  n*555  n*5555 .......       

     n/5   n/55  n/555  n/5555  ......

이것은 num이 1개씩 늘어가고

n+1

n-1 은 num 이 2개 늘어나는 방식으로 d[n +-*/ ??] 를 채워나갔다.

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int d[32001] = { 0 };
 
 
void go(int cur_su, int cur_num, int n)
{
    d[cur_su] = cur_num;
    //cout << cur_su << ' ' << cur_num << '\n';
    
 
    int tmp_su = n;
    int tmp_num = cur_num + 1;
 
    while (cur_su + tmp_su <= 32000 && tmp_num <= 8)
    {
        if(d[cur_su + tmp_su] > tmp_num)
            go(cur_su + tmp_su, tmp_num, n);
        tmp_su = tmp_su * 10 + n;
        tmp_num++;
    }
 
    tmp_su = n;
    tmp_num = cur_num + 1;
 
    while (cur_su - tmp_su >= 0 && tmp_num <= 8)
    {
        if (d[cur_su - tmp_su] > tmp_num)
            go(cur_su - tmp_su, tmp_num, n);
        tmp_su = tmp_su * 10 + n;
        tmp_num++;
    }
 
    tmp_su = n;
    tmp_num = cur_num + 1;
    while (cur_su * tmp_su <= 32000 && tmp_num <= 8)
    {
        if (d[cur_su * tmp_su] > tmp_num)
            go(cur_su * tmp_su, tmp_num, n);
        tmp_su = tmp_su * 10 + n;
        tmp_num++;
    }
 
    tmp_su = n;
    tmp_num = cur_num + 1;
    while (cur_su / tmp_su > 0 && tmp_num <= 8)
    {
        if (d[cur_su / tmp_su] > tmp_num)
            go(cur_su / tmp_su, tmp_num, n);
        tmp_su = tmp_su * 10 + n;
        tmp_num++;
    }
 
    tmp_su = cur_su + 1;
    tmp_num = cur_num + 2;
    if(tmp_su <= 32000 && tmp_num <= 8 && d[tmp_su] > tmp_num)
    {
        go(tmp_su, tmp_num, n);
    }
 
    tmp_su = cur_su - 1;
    tmp_num = cur_num + 2;
    if (tmp_su >= 0 && tmp_num <= 8 && d[tmp_su] > tmp_num)
    {
        go(tmp_su, tmp_num, n);
    }
}
 
 
int solution(int n, int num)
{
    for (int i = 0; i <= 32000; i++)
        d[i] = 9;
 
    go(0, 0, n);
    //go(22222, 5, n);
    if (d[num] == 9)
        return -1;
    return d[num];
}
 
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
/*
    int n = 8;
    int num;
    for (int i = 0; i < 10; i++)
    {
        cin >> num;
        cout << solution(n, num) << '?';
    }
    */
 
    int n = 8;
    int num = 11095;
    cout << solution(n, num) << '?';
 
 
}

이렇게 말이다.

 

BUT 틀렀다. 반례는 저기 있는 8, 11095 이다.

왜냐면 이것의 답은

88888 / 8 - 8 - 8  인데

d[88888] 을 어떻게 집어넣을것이냐???? 안된다.

 

그러면 9*9*9*9*9*9*9*9  5천만정도인데 데 d[5천만]? 메모리 살려 ㅠㅠ.

 

근데 답은 DFS방식으로 그냥 생각보다 편하게 구하자.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#define pii pair<int, int>
using namespace std;
 
int ans = 987654321;
 
void go(int cur_su, int cur_cnt, int n, int num)
{
    if (cur_cnt >= 9)
        return;
 
    if (cur_su == num)
    {
        ans = min(ans, cur_cnt);
        return;
    }
 
 
    int tmp_su = n;
    int tmp_cnt = cur_cnt + 1;
    while (tmp_cnt <= 8)
    {
        go(cur_su + tmp_su, tmp_cnt, n, num);
        go(cur_su - tmp_su, tmp_cnt, n, num);
        go(cur_su * tmp_su, tmp_cnt, n, num);
        go(cur_su / tmp_su, tmp_cnt, n, num);
 
        tmp_su = tmp_su * 10 + n;
        tmp_cnt++;
    }
 
 
 
 
}
 
int solution(int n, int num)
{
    go(0, 0, n, num);
 
    if (ans == 987654321)
        return -1;
    else
        return ans;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
 
 
 
    int n = 8;
    int num = 11095;
    cout << solution(n, num) << '?';
 
}
 
 

디용? 잠시만 그러면 + 1은 어떻게 처리하는건가??

특히 8891 8은 어떻게 할것이냐

8888 + 8/8 + 8/8 + 8/8 안되는데???

 

 

=> +3 을 꼭 8/8 + 8/8+ 8/8로 나타내지 않아도 된다.

(8+8+8)/8로 절약할수 있다.

즉 (8+8+8)/8+8888 로 8개만에 만들 수 있다.... +1을 미리 해줘서 사칙연산만 사용해도 충분히 전부 탐색이 가능하다.