n으로 표현 // DP

#include <string>
#include <vector>
#include <set>
#include <iostream>
using namespace std;

set<int> cache[10]; //전역 배열
int N_;
set<int> solve(int n){  //재귀
    if(!cache[n].empty()){ // dp 특징
        cout<<"dd"<<n<<endl;
      return cache[n]; // 비어있지 않으면  
    } 
    int num = 0;
    for(int i=0; i<n; i++) num= num*10 + N_; // NNNN..
    set<int> temp;
    temp.insert(num);
    for(int i=1; i<n; i++){ // (N)*(NNNNN) 괄호 짓기
        int j = n-i;
        cout<<"first i"<<n<<endl;
        auto s1 = solve(i);
        cout<<"first j"<<n<<endl;
        auto s2 = solve(j);
        for(int n1:s1){ //사칙연산
            for(int n2:s2){
                temp.insert(n1+n2);
                temp.insert(n1-n2);
                temp.insert(n1*n2);
                if(n2 !=0) temp.insert(n1/n2);
            }
        }
    }
    return cache[n] = temp; //전역 배열에 저장
}

int solution(int N, int number) {
    int answer = 0;
    N_ = N;
    for(int i=1; i<=8; i++){
        cout<<"real start "<<i<<endl;
        solve(i);
        if(cache[i].find(number)!= cache[i].end()) return i;
    }
    return -1;
}

dp 는 전역배열 만들고

전역배열에 저장된것을 이용한다.!