N으로 표현(프로그래머스)

프로그래머스 링크

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

풀이

• Dynamic Programming에 관한 문제이다, 임시 객체에 무엇을 저장 할 지에 대해 먼저 생각
• 어떤 부분을 한 번 풀었다면 그 부분에 대한 중복된 계산을 하지 않도록 한다.
• unordered_set을 통해 정렬되지 않은 키 값에 빠르게 근접하도록 한다.
• 모든 사칙 연산, NNN… 에 대한 수를 임시 변수에 삽입하여 N[k] = N[i] + N[j]에 관한 계산 진행
• 만약, number와 같은 숫자가 N[k] 셋에 존재한다면? k - 1 반환, 없다면 -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);
                if(n1 > n2)
                    res.insert(n1 - n2);
                res.insert(n1 * n2);
                
                if (n1 >= n2) 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;
}