ABC 045C たくさんの数式 を Python で解いてみた。

はじめに

今回はAtCoderの『ABC 045C たくさんの数式』をPythonで解いてみました。

問題

ABC045C-たくさんの数式

方針

• "+"が入るパターンを全探索（再帰）
• "+"が"入る時"と"入らない時"で分岐
• 文字列を数字化して計算する

実装

準備として

• 入力
• 再帰のために桁数の取得

これらを行います

s = input()
n = len(s)

次に再帰の関数を定義していきます。

• 文字列がs[0],s[1],s[2]…s[n-1]という順に全探索し終えたタイミングでそれぞれ文字列を数値化して計算するように書く。

• 合計値を出力するので戻り値を分岐した数式の和となるように設計する

def dfs(i, f):
    # 全検索が終了
    if i == n - 1:
        # 文字列を数値化して計算する
        return sum(list(map(int, f.split("+")))
    # 分岐した数式の和
    return dfs(i + 1, f + s[i + 1]) + dfs(i + 1, f + "+" + s[i + 1])

最終的に再帰の関数に初期値を設定してprintで出力します。

print(dfs(0, s[0]))

答え

def dfs(i, f):
    if i == n - 1:
        return sum(list(map(int, f.split("+")))
    return dfs(i + 1, f + s[i + 1]) + dfs(i + 1, f + "+" + s[i + 1])
s = input()
n = len(s)
print(dfs(0, s[0]))

今回は『全検索(再帰)』 『文字列の数値化』が分かれば解けた問題でした。