모노디지털 표현

백준 2287번: 모노디지털 표현

아이디어

숫자 i개 사용해서 만든 수 +*-/ 숫자 j개 사용해서 만든 수 = cache[i+j]
뺄셈, 나눗셈은 순서에 영향을 받기 때문에 뒤집어서도 해준다.
이렇게 하면 괄호 생각 안하고 풀어도 됨.

코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int k, n;
    cin >> k >> n;
    vector<int> v{k};
    for (int i = 1; i < 8; i++) {
        v.push_back(v[i-1]*10+k);
    }

    while (n--) {
        int x;
        cin >> x;
        set<int> cache[9];

        for (int i = 0; i < 8; i++) {
            cache[i+1].insert(v[i]);
        }

        for (int i = 1; i < 9; i++) {
            for (int j = 1; j < 9; j++) {
                if (i+j > 8) continue;
                for (int a : cache[i]) {
                    for (int b : cache[j]) {
                        cache[i+j].insert(a+b);
                        cache[i+j].insert(a-b);
                        cache[i+j].insert(b-a);
                        cache[i+j].insert(a*b);
                        if (b) cache[i+j].insert(a/b);
                        if (a) cache[i+j].insert(b/a);
                    }
                }
            }
        }

        int ans = -1;
        for (int i = 0; i < 9; i++) {
            if (cache[i].find(x) != cache[i].end()) {
                ans = i;
                break;
            }
        }
        if (ans == -1) cout << "NO\n";
        else cout << ans << '\n';
    }

    return 0;
}

여담

아니 진짜 개어렵다.. 프로그래머스 스킬체크 레벨 3 뚫다 얘한테 컷당하고 화나서 풀어봄.