[Programmer]Nで表す

コードテスト練習-Nと表示

解き直した。

まず,この問題は繰り返されるサブ問題の形態を見ることができるので,動的計画法を用いるべきである.
Nで何をするべきかではなく、「k個の数字で生成可能な数を順番に求める方法」を使うべきです.これは、問題でkを8に制限しているからかもしれません.
では、ダイナミックプランニング法を使って何ができるのでしょうか.→3個でできる数を求めるとき、2個でできることと1個でできることの組み合わせ→何ができるか.

k個N(

)

1개로 -> 5
2개 -> 55 ,5/5, 5*5, 5+5
3개 -> 555, ( 1개로만들수 있는 +2개로만들) ,( 2개로 만들 수 있는 것, 1개로 만들 수 있는 것 )

なぜ動的計画法になったのか.

3 : (2+1)(1+2)

4 : (3+1)(2+2)(1+3)

5 : (4+1)(3+2)(2+3)(1+4)

これは,k個とi−k個を組み合わせた結果である.

解き直した。

この問題は以前やったことがあるし、これ以上できなかった.
(25分の苦悩…今日はやり直しの問題でしたが、いろいろな困難を感じ、長時間の苦悩をするのは難しいと思いました)
前回とあまり差がないようです.そのため、すぐに他の人の答えが見えました.ダイナミックプログラミングは常に斬新で困難です.
前回のように~~(間違い)執着に集中している部分~~という部分です

ある数字を生成するために、y 1、y 2、y 3...私たちはこれらのコンポーネントが必要だと思います.そして、これらのコンポーネントを作成する最小数を見つけて、それらを使いましょう~~(つまり、これはダイナミックプランニング法ではありませんか?)

もしそうなら、y 1、y 2、y 3を四則演算する方法の数を考慮すべきであり、

.

どうやって解くの???

ですが、問題を解決するには、逆に考えなければなりません.💥💥...!!
1回

Nで生成できる数→2回Nで生成できる数→3回Nで生成できる数…このように

ただし、この場合、i回で作成できる数については、次のようなルールがあります.
1回の

Nで作成できる数

1番セット:5

2回の

Nで作成できる数

2号セット:(55)(5+5=1)(5*5=25)(5-5=0)=55を除き、1号セットの値を利用した様子が見られます.

3回の

Nで作成できる数:考えてみてください.

第3セット:(555)(5+/-55)(5+/-10)(5+/-1)(5+/-25)(5+/-*0)

ここは見えますか?iを使用して作成する場合、

i回使用

nの数

i-kおよびkにおけるデジタル演算

import java.util.*;
class Solution {
    public StringBuilder sb = new StringBuilder("");
    public Set<Integer>[] sets = new Set[9]; 
    public int solution(int N, int number) {
        int answer = 0;
        // init sets : 각 set[i]는 i+1번째 세트 : i+1개로 만들 수 있는 "숫자"를 뜻한다. 
        for(int i=0;i<sets.length;i++)
            sets[i] = new HashSet<>(); 
        // N을 1번 -> 8번 이용하여만들수 있는 수 중, number와 같은 경우, 즉시 리턴
        for(int i=1;i<=8;i++){
            // 결국 sb는 하나씩 N을 추가 
            sb.append(Integer.toString(N));
            sets[i].add(Integer.parseInt(sb.toString()));
            // NNN...(i개) 이 number와 같은 경우에는 makeSet을 돌지 않도록 shortcut을만들었다
            if(sets[i].contains(number)||makeSet(i,number)) {
                answer = i;
                break;
            }
        
        }
        if(answer==0) answer =-1;
        return answer;
    }
    
    // number를 찾게 되면 
    public boolean makeSet(int i,int number){
        int temp =0;
        // i-k번째 세트와 k번째 세트를 사용 
        for(int k=1,c=i-k;k<=i/2;k++,c--){
            for(int ke:sets[k]){
                for(int ce:sets[c]){
                    // 4가지 연산 ( 이 때, /와 -의 경우, 순서가 바뀌는 경우도 서로다른 경우다 )
                    sets[i].add(ke+ce);
                    sets[i].add(ke*ce);
                    if(ce!=0)sets[i].add(ke/ce);
                    if(ke!=0)sets[i].add(ce/ke);
                    sets[i].add(ke-ce);
                    sets[i].add(ce-ke);
                }
            }
            if(sets[i].contains(number)) return true; 
        }
        return false;
    }
}

テスト1〉合格(1.60 ms,71.3 MB)
試験2〉合格(0.08 ms,77.3 MB)
試験3〉合格(0.19 ms,76.2 MB)
試験4〉合格(23.87 ms,81.2 MB)
試験5〉合格(10.74 ms,81.8 MB)
試験6〉合格(0.77 ms,74.7 MB)
試験7〉合格(0.57 ms,74.3 MB)
試験8〉合格(5.73 ms,82.5 MB)
試験9〉合格(0.05 ms,74 MB)

のような「動的計画法」の問題では,i−1の値(i−1の値)を利用する問題がしばしばあるようである.全く同じではありませんが、次の問題にも似ている点があります.

Count Sorted Vowel Strings - LeetCode