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

이것저것 참고해가면서 풀었다........🫠

N = 5라면

5를 1개 사용
5

5를 2개 사용
55, 5+5, 5-5, 5/5, 5*5

5를 3개 사용
555
5+(5+5), 5+(5-5), 5+(5/5), 5+(55),
5(5+5), 5(5-5), 5 (5/5), 5(55),
5-(5+5), 5-(5-5), 5-(5/5), 5-(55),
5/(5+5), 5/(5-5), 5/(5/5), 5/(55),
(5+5)/5, (5-5)/5, (5/5)/5, (55)/5,
(5+5)-5, (5-5)-5, (5/5)-5, (55)-5

이렇게 사용할 수 있다. 그래서 자세히 보면

N1 = N,
N2 = N1ㅁN1, NN
N3 = N1ㅁN2, N2ㅁN1, NNN
...
NK = Ni + N(K-i), N(i+1) + N(k-i-1)...,Nk
이렇게 나타낼 수 있다. (K는 N을 사용한 갯수, ㅁ은 사칙연산)

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

int getNN(int N, int idx){
    int result = 0;
    for(int i=0;i<idx;i++){
        result = result*10 + N;
    }
    return result;
}

int solution(int N, int number) {
    if(N == number) return 1;
    vector<unordered_set<int>> dp(9);
    dp[1].insert(N);
    
    for(int k=2;k<=8;k++){
        for(int i=1;i<k;i++){
                for(int a: dp[i]){
                    for(int b: dp[k-i]){
                        dp[k].insert(a+b);
                        dp[k].insert(a-b);
                        dp[k].insert(a*b);
                        if(b != 0) dp[k].insert(a/b);
                    }
                }
        }
        dp[k].insert(getNN(N,k));
        if(dp[k].count(number))return k;
    }
    return -1;
    
}