[프로그래머스 / C++] N으로 표현 : DP

참고

#include <unordered_set>
#include <vector>
using namespace std;

// N을 k번 써준 것 if k=2 -> NN
int getNN(int N, int k){
    int res=0;
    int mul=1;
    for(int i=1;i<=k;i++){
        res+=N*mul;
        mul*=10;
    }
    
    return res;
}

int solution(int N, int number) {
    if(N==number) return 1;
    
    //최소 8개까지만 사용해야 함.
    //DP[i]=N을 i번 사용해 만들 수 있는 숫자들
    vector<unordered_set<int>> DP(9); 
    
    DP[1].insert(N); //1번 사용했을 경우
    
    //k회 사용시
    for(int k=2;k<=8;k++){
        
        //i+j==k 일 때 되는 DP끼리 연산할 수 있음
        for(int i=1;i<k;i++){
            for(int j=1;j<k;j++){
                if(i+j!=k) continue; 
                for(auto a: DP[i]){ //i로 만들 수 있는 것들
                    for(auto b: DP[j]){ //j로 만들 수 있는 것들
                        //사칙연산 4개
                        DP[k].insert(a+b);
                        DP[k].insert(a*b);
                        if(a-b>0) DP[k].insert(a-b); //음수는 나오면 나중에 더하고 빼다가 중복됨.
                        if(a/b>0) DP[k].insert(a/b);
                    }
                }
            }
        }
        
        DP[k].insert(getNN(N,k)); 
            
        if(DP[k].count(number)) //set안에 number가 존재하면
            return k;
        
    }
    
    return -1;
    
    
}