N으로 표현 C++

 

문제 설명

입출력 예

N                                                             number                                                                    return

5	12	4
2	11	3

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

 

 

#include <string>
#include <vector>
#include <cmath> 
#include <unordered_set> // unorderd_set사용

using namespace std;

int get_basic(int N, int cnt) {
    int res = 0;
    
    while (cnt > 0)
    {
        cnt -= 1;
        res += N * pow(10, cnt);
    }
    return res;
}


int solution(int N, int number) {
    int answer = -1;
    vector<unordered_set<int>> s(8);
    int idx=1;
    
    if(N == number)
    {
        return 1; 
    }
    for(auto &x : s)
    {
        x.insert(get_basic(N,idx));
        idx ++;
    }
    
    for (int i=1; i<8; i++) 
    { 
        for (int j=0; j<i; j++) {
            for (const auto & op1 : s[j]) {
                for (const auto & op2 : s[i-j-1]) {
                    s[i].insert(op1+op2);
                    s[i].insert(op1-op2);
                    s[i].insert(op1*op2);
                    
                    if (op2 != 0)
                        s[i].insert(op1/op2);
                }
            }
        }
        if (s[i].find(number) != s[i].end()) {
            answer = i+1;
            break;
        }
    }
    return answer;
}

 

=> DP를 사용하여 풀어야하는 문제입니다. 

=> 5로 만들 수 있는 숫자에는 55, 555, 5555, 5555, 55555, 555555, 5555555, 5555555 이 포함됩니다. (사칙연산이 아닌데도 포함됨.)

=> 위 사항을 염두에 두고 아고리즘을 짜야합니다.