[解析アルゴリズムプール]Programmers Nとして表示

生まれながらにしてDPが嫌いな病気があり、
延び延びになっていたDPが今日やっと始まりました
初めての解ではありませんが、プログラミングアルゴリズムではDPだけが唯一で、残りの0/6の様子が好きではないので、今日は2つの問題を解決しました.そのうちの1つを位置づけたいと思います.

プログラマNとして表す

質問リンク
12=(55+5)/5などN,numberが与えられると,Nを利用してnumberを表すだけで,その中で最も少ないNを見つければよい.

制限とI/O

私の答え

最初は1から与えられた数字までbottom-upで解決したいと思っていました.iを表現するために、先に求めた記憶[1~i-1]の内容を利用して最大値を求めるように求めた記憶[i]は、再びi+1を求める形で解決しようと試みる!
結果は間違っていた!
私の薄っぺらなDP知識に依存しているからか、このbottom-up方式は答えに指定されていて、規則性を発見するためにあちこち書いても、特別な法則が分からないのに、どうしてだめなのか、他の方法を試してみなかった.
最終的にはブログ記事を参考にして、新しい方法でアクセスして解決することができます.

ソリューション

通る解答の核心の概念は想像するより簡単です
与えられた整数Nは集合(i)と呼ばれ、集合(n)が作成されたときに用いられる.

セット(n-1)&セット(1)

セット(n-2)&セット(2)

セット(n-3)&セット(3)
...

セット(1)&セット(n-1)

これはn個を用いてn個の数の集合を作成し,集合(n)を完成させる方式である.
ここには余計な配慮が必要なやつがいて、N羅列のN N Nと同じ形式の整数です.
説明が抽象的に見えるので、具体的な例で説明しましょう.
N=2ならnumber=11!

2を使用して整数を作成できます:

2つの

2で作成できる整数:2+2、(2-2)、2*2、2/2、22
この場合、2-2=0で、私たちが探している数字は1以上32000以下の整数で、除外できます!
すなわち、2つの2を用いる生成可能な整数は、22、4、1の3種類:

である.
3つの

2を使用して作成できる数

加算)2+222+4,2+1,(22+2,22+4,22+1)

マイナス記号)2-22、2-4、2-1、22-2、4-2、1-2

積)222、24、21、(222、42、12)

.

除算)2/22、2/4、2/1、22/2、4/2、2/1

そして222!

しかし乗算と加算の交換法則は成立するので、同じ演算結果が2回出ます!括弧の中の数字は計算しないでください!
また、減算については、演算結果が1未満であれば、それを排除することができ、除算演算時に除算が0のエラーが発生することを回避することができる.
このようにして1から8方向に2次元ベクトルを完成させ、計算結果がnumberの場合、検索を停止し、正しい答えを返すようにコードを記述します.

コード#コード#

#include <vector>
#include <algorithm>

using namespace std;

// N을 times 번 이어붙이 수 반환
int getConnectedNumber(int N, int times){
    int ans = 0;

    for (int i = 0; i < times-1; ++i) {
        ans *= 10;
        ans += (N * 10);
    }
    ans += N;

    return ans;
}

// 사칙 연산을 통해 만들 수 있는 수 추가, number 인지 확인하면 반환
bool basicOperating(vector<vector<int>> & sets, int a, int b, int number){
    int n = a+b;

    for (int i = 0; i < sets[a].size(); ++i) {
        for (int j = 0; j < sets[b].size(); ++j) {
            int subtract, divide, sum, multiple;
            subtract = sets[a][i] - sets[b][j];
            divide = sets[a][i] / sets[b][j];

            // 뺀 값과 나눈 값은 1 이상일 때에만 적용
            if (subtract >= 1) sets[n].push_back(subtract);
            if (divide >= 1) sets[n].push_back(divide);

            if (a >= b) {
                sum = sets[a][i] + sets[b][j];
                multiple = sets[a][i] * sets[b][j];

                sets[n].push_back(sum);
                sets[n].push_back(multiple);
            }

            // 찾던 수라면 탐색 중단하고 반환
            if (subtract == number || divide == number || sum == number || multiple == number) return true;

        }
    }

    return false;
}

int solution(int N, int number) {
    int answer = 0;
    bool found = false;
    vector<vector<int>> numsUsingN(9);
    
    vector<int> base = {N, N*10 + N, N+N, N*N, N/N};

    if (base[0] == number) return 1;
    numsUsingN[1].push_back(N);
    
    for (int i = 1; i < base.size() ; ++i) {
        if (base[i] == number) return 2;
        numsUsingN[2].push_back(base[i]);
    }
    
    numsUsingN[2].erase(unique(numsUsingN[2].begin(), numsUsingN[2].end()), numsUsingN[2].end());

    for (int i = 3; i <= 8 ; ++i) {
        int connected = getConnectedNumber(N, i);

        if (connected == number) {
            found = true;
            break;
        }else{
            numsUsingN[i].push_back(connected);
        }

        for (int j = i-1; j >= 1 ; j--) {
            if (basicOperating(numsUsingN, j, i-j, number)){
                answer = i;
                found = true;
                break;
            }
        }

        if (found) break;
    }

    if (!found) answer = -1;

    return answer;
}

参考資料