🌞 느낀점

dp는 역시 어렵다..
처음부터 감을 잡지 못하고 어떻게 배타집합을 구해야 할지를 몰라서 쩔쩔 맸다.
그래서 약간의 힌트를 얻고 다시 시작을 해서 배타집합들을 구할 수 있었다.
하지만 이를 코드로 나타 낼수가 없어서 포기를 했다.

아래는 포기를 한 이후에 내 스스로 코드를 분석해본 내용이다.

🌞 코드 및 분석

N의 사용 횟수를 기준으로 경우의 수를 나누어 보면,
1~8개의 N을 사용 할 수 있다.
여기서 8개인 이유는 N은 최대 8이하라는 조건이 걸려 있기 때문이다.

여기서 만약에 N이 5라고 하고, 5가 나온 횟수를 i라고 할 때
i=1 : 5
i=2 : 55, 5+5, 5-5, 5*5, 5/5
i=3 : 555, i=2 일때와 i=1 일때의 사칙연산의 합집합
i=4 : 5555, i=3 일때와 i=1 일때의 사칙연산의 합집합, i=1 일때와 i=3일때의 사칙연산의 합집합,
i=2 일때와 i=2 일때의 사칙연산의 합집합
...
i=8 ...
모든 경우의 수는 이렇게 나온다.

이러한 모든 경우의 수를 확인하면서 i=1일 때를 시작으로 i=8일 때 까지 모든 경우의 수를 만들면서 그 결과가 number와 값이 같은지를 확인한다.

만약에 8을 초과하게되면 -1을 출력한다.

unordered_set은 map과 비슷하지만, key값만 있는 map이라고 생각하면 좋을 것 같다.
이 컨테이너를 이용한 이유는 중복된 값은 제거하면서 가장 효율적인 컨테이너이기 때문이다.

cache는 unordered_set 타입의 배열이다. 이 배열에는 위에서 말했던 i=1, i=2, ... i=8 일 때의 값들이 각각의 배열에 요소로 들어 갈 것이다.

이렇게 해주는 이유는 값들을 기억하면서 그 값들을 다시 재계산 하지 않고, 위의 값들을 이용하여 다음 배열의 값들을 알아내기 위해서이다.

먼저 num이라는 int형 변수에 5, 55 ,555 등의 연속적인 수를 추가해준다.
그리고 반복문을 돌면서 i에 해당하는 n값을 이용하여 사칙연산이 가능한 쌍을 만들어 사칙연산을 해주고 그 값을 unordered_set에 저장을 한다. 그리고 cache에 여태까지 계산해온 것이 다 저장되어있는 unorederd_set을 cache에 한 배열에 저장해준다.

그리고 cache에서 number 값이 있는지를 확인하고, 그 값이 있다면 i 값을 리턴하고 종료한다. 이런 과정을 다 하고, 8번이 넘어서도 없다면 -1을 리턴한다.

#include <string>
#include <vector>
#include <unordered_map>

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;
}