[promgrammers] N으로 표현

문제링크 입니다

🚀 [N으로 표현] Lv. 3 문제

N과 사칙연산 만으로 Number를 표현할 수 있는 것 중 최소한의 N을 사용한 수를 출력하는 문제입니다.
N을 사용하여 표현 할 수 있는 모든 값을 vector[N]에 저장하고 이전 벡터 값들을 통해 vector[N] 을 채워나가며 문제를 해결합니다.
중복을 방지하기 위해 set을 사용하였습니다.

💎 전체 코드는 다음과 같습니다.

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

// DP 로 해결한다.
int solution(int N, int number) {
    if(N == number) return 1;
    // set을 사용하여 값의 중복을 막는다.
    vector<set<int> > vec(9);
    // N을 하나만 사용하면 N만 된다.
    vec[1].insert(N);
    string Nstring = to_string(N);
    // 모든 벡터에 N을 덫 붙인 숫자를 더해준다.
    // ex) N이 5이면 1 -> 5,  2-> 55, 3-> 555
    for(int i=2; i<9 ; i++){
        Nstring += to_string(N);
        vec[i].insert(stoi(Nstring));
    }

    // 이전 벡터의 값들을 사칙연산을 통해 계산해 현재 식에 저장.
    for(int i=2; i<9; i++){
        for(int j=1; j<=i; j++){
            for(set<int>::iterator it = vec[j].begin(); it!=vec[j].end(); it++){    
                for(set<int>::iterator it2 = vec[i-j].begin(); it2!=vec[i-j].end(); it2++){
                    vec[i].insert((*it) + (*it2));
                    vec[i].insert((*it) - (*it2));
                    vec[i].insert((*it) * (*it2));
                    if(*it2 != 0)
                        vec[i].insert((*it) / (*it2));        
                }
            }
        }
        if(vec[i].find(number) != vec[i].end()) return i;                     
    }
    return -1;
}