ABC 079C Train Ticket をPythonで解いてみた。

はじめに

今回はAtCoderの『ABC 079C Train Ticket』をPythonで解いてみました。

問題

ABC 079C-Train Ticket

方針

• "+"か"-"が入るパターンを全探索（再帰）
• "+"と"-"で分岐
• 合計が7にならば数式を出力させる

実装

準備として入力を変数に代入します

s = input()

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

• "+"と"-"で分岐するように全探索し、その中に合計7になる数式が見つかれば式を出力して終了する。
• 合計値を出力するので戻り値を分岐した数式の和となるように設計する

def dfs(i, f, sum):
    # 全検索
    if i == 3:
        # 合計が7になる数式
        if sum == 7:
            # 式を出力して終了
            print(f + "=7")
            exit()
    else:
        # + と - で分岐する
        dfs(i + 1, f + "+" + s[i + 1], sum + int(s[i + 1]))
        dfs(i + 1, f + "-" + s[i + 1], sum - int(s[i + 1]))

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

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

答え

def dfs(i, f, sum):
    if i == 3:
        if sum == 7:
            print(f + "=7")
            exit()
    else:
        dfs(i + 1, f + "+" + s[i + 1], sum + int(s[i + 1]))
        dfs(i + 1, f + "-" + s[i + 1], sum - int(s[i + 1]))
s = input()
dfs(0, s[0], int(s[0]))

今回は『全検索(再帰)』 『条件式』が分かれば解けた問題でした。