[補助]DFS:14888挿入演算子(BaekJoon)

9424 ワード
白駿 テキストリンク
質問リンク
▼▼▼▼草
与えられた演算値は、+がx個〜y個に等しい形式で与えられる.この問題をDFSバックトラックでどのように解決すればいいか分かりません.
通常のDFSのようにするために、アクセスチェックのために数値ごとに配列を作成しました.
🛠 マイコード
def DFS(index, val):
    global mx, mn
    if index == n-1:
        mx = max(mx, val)
        mn = min(mn, val)
        return
    for i in range(len(oper)):
        if check[i]:
            continue
        check[i] = True
        if oper[i] == 0:
            DFS(index + 1, val + num[index+1])
        elif oper[i] == 1:
            DFS(index + 1, val - num[index+1])
        elif oper[i] == 2:
            DFS(index + 1, val * num[index+1])
        else:
            DFS(index + 1, val//num[index+1] if val > 0 else -((-val)//num[index+1]))
        check[i] = False

n = int(input())
num = list(map(int, input().split()))
operator = list(map(int, input().split()))
oper = []
for i in range(len(operator)):
    for j in range(operator[i]):
        oper.append(i)

check = [False]*len(oper)

mx = int(-1e9)
mn = int(1e9)
sm = num[0]
DFS(0, sm)
print(mx)
print(mn)
📝 整理する
  • 与えられた演算子の形状を保つために、演算子の個数をパラメータに渡すことで解く方法がある.->下記リンク参照
    • 🎈 リファレンス
  • rebasあなたのブログ
  • これが就職のためのコードテストwith python
    • あなたの最初のポストを書く方法
    どのようにコードの17行でシンプルなツイッターボットを構築する