N으로 표현

programmers.co.kr/learn/courses/30/lessons/42895

코딩테스트 연습 - N으로 표현

 

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

using namespace std;
int N;
unordered_set<int> cache[10];

unordered_set<int> dp(int n){
    if(!cache[n].empty()) return cache[n];
    int num =0;
    for(int i=0; i<n; i++) num = 10*num +N;
    unordered_set<int>res;
    res.insert(num);
    for(int i=1; i<n; i++){
        int j = n-i;
        auto s1 = dp(i);
        auto s2 = dp(j);
        for(int n1:s1){
            for(int n2:s2){
                res.insert(n1+n2);
                res.insert(n1-n2);
                res.insert(n1*n2);
                if(n2!=0) res.insert(n1/n2);
            }
        }
    }
    return cache[n]=res;
}

int solution(int _N, int number) {
    int answer = 0;
    N=_N;
    for(int i=1; i<=8; i++){
        dp(i);
        if(cache[i].find(number)!=cache[i].end()) return i;
    }
    
    return -1;
}

특정 숫자 예를 들어 5 라고 하면 

num = 5, 55, 555, 5555, 55555, ... 55555555 이런식으로 1에서 8자리 까지의 숫자를 각각 구해서 dp에 넣어준다. 

dp 에서는 5가 n 개일 때의 연산을 모두 cache라고 하는 unordered_set 에다가 넣어주게 된다. 

예를 들어 5가 2개일 경우에는 55와 1의자리수 5 두개와 연산하는 경우가 있다. 

5가 3개일 때는 555 와 55와5, 5와55 , 5를 3개와 연산하는 경우가 있다.

dp(555) = (dp(55) 연산 dp(5)) & (dp(5) 연산 dp(55)) & 555 이런식으로 작은 문제들을 하나씩 풀어나가 다보면 number에 만족하는 연산결과를 포함하는 set이 나올 수 있다.