[プログラマ]DP-Nと表示

6226 ワード
アルゴリズム#アルゴリズム# DP programmers テキストリンク

質問リンク


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

問題を解く


Nと4則演算のみで数字を表す方法では、Nの使用回数の最大値を求める.
条件
ピークが
  • の場合、-1を返し、
    • を返します.
  • Nは1以上9以下、番号は1以上32000以下
    • である.
    IN
    N 

number
    OUT
    N을 최소개 사용하여 number로 표현할때 N의 사용횟수

    に答える


    DPは専門のアルゴリズムの授業の後で初めて解いたので、よく知らないし、難しいです.
    わかりませんが、ブログ記事(https://gurumee92.tistory.com/164)を参照してください.
    Nを使用してnumberを最大8回作成します.
    例1に示すように、N=5、number=12の場合
    **set1** 5를 1번 사용하는 경우 → 5

**set2** 5를 2번 사용하는 경우 → 5를 2번 붙힌 55와 5+5, 5-5, 5*5,  5/5

→ 이때 set2는 5를 2번 붙히기 + set1의 원소 (+-*/) set1의 원소 

**set3** 5를 3번 사용하는 경우 → 5를 3번 붙힌 555와 5+55, 5-55, 5*55, 5/55, 55+5, 55-5, 55*5, 55/5

→ 이때 set3는 5를 3번 붙히기 + set1의 원소 (+-*/) set2의 원소 + set2의 원소 (+-*/) set1의 원소
    →setnを一般化し、
    :setnは5回+set 1の要素(+-/)set n-1の要素+set 2の要素(+-/)set n-2の要素+.+を貼り付けます.set n-1の要素(+-*/)set 1の要素
    だから~

  • 8セット作成

  • 各セットにn回iを追加

  • ドア回りにiの1番目のセットにjの1番目のセットの要素(+-*/)i-j-1のセットの要素値を追加する
    3.1このセットにnumberに対応する値がある場合、解答値を更新して切り離す
    • 近似解でいいです.
    def solution(N, number):
    answer = -1
    
    if N == number:
        return 1
    
    #n을 1번부터 8번 사용한 set의 초기화
    s = [set() for _ in range(8)]
    for i,x in enumerate(s, start=1):
        x.add(int(str(N) * i))
    
    for i in range(1, 8):
        for j in range(i):
            for op1 in s[j]:
                for op2 in s[i-j-1]:
                    s[i].add(op1 + op2)
                    s[i].add(op1 - op2)
                    s[i].add(op1 * op2)
                    if op2 != 0:
                        s[i].add(op1 // op2)
        if number in s[i]:
            answer = i + 1
            break
    return answer
    varとletとconstとは何ですか?どのような地獄これらの3つの違いですか?
    redis構成マスタースレーブサーバ