[알고리즘C++]N으로 표현

오늘의 문제

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

N으로 표현

나의 풀이

#include <string>
#include <vector>
#include <set>

using namespace std;

int solution(int N, int number) {
    const int minN = 9;
    vector<set<int>> num(minN);
    int NN = 0;
    for(int i=0;i<minN;i++){
        num[i].insert(NN);
        NN = NN*10 + N;
    }
    
    for(int i=0;i<minN;i++){
        for(int j=0;j<minN;j++){
            if(i + j < minN){
                for(auto& rnum : num[i]){
                    for(auto& lnum : num[j]){
                        num[i+j].insert(lnum+rnum); 
                        num[i+j].insert(lnum-rnum); 
                        num[i+j].insert(lnum*rnum);
                        if(rnum != 0)
                            num[i+j].insert(lnum/rnum); 
                    }
                }
            }
        }
        if(num[i].find(number) != num[i].end()){
            return i;
        }
    }
    return -1;
}

모범 답안

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

using namespace std;

int N;
unordered_set<int> cache[10];
unordered_set<int> solve(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 = solve(i);
        auto s2 = solve(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) {
    N = _N;
    for (int i = 1; i <= 8; i++) {
        solve(i);
        if (cache[i].find(number) != cache[i].end()) return i;
    }
    return -1;
}

배울 점

• 어떻게 풀어야할 지 감이 안잡혀 코드를 보게 되었다. 계산에 사용되는 정수를 set에 저장해두고 연산을 하여 다시 넣는 방법을 쓸 수 있다니 놀랍다. 앞에서 푼 문제인 dictionary 문제에서 없는 문자인 경우 추가를 했던것이 기억난다
• 연산을 할 때 연산되어야 할 숫자의 규칙이 있다면 연산 되어야 할 숫자의 배열에 새로 추가하는 방법이 있다는 것을 기억하자