Submission #3011888

---

Source Code Expand

S = input()

dp = [[[-1 for k in range(len(S))] for j in range(len(S))] for i in range(len(S))]


def rec(idx, cur, t):
    """

    :param int idx: 現在見ているインデックス
    :param int cur: 最後に文字を変更したインデックス(カーソルの位置)
    :param int t:'('が')'よりどれだけ多いか
    :return int res: (idx, cur, t)における操作回数の最小値
    """
    if idx == len(S) and t == 0:
        return cur
    if t < 0 or idx == len(S) and t != 0:
        return 1000
    if dp[idx][cur][t] != -1:
        return dp[idx][cur][t]

    if S[idx] == "(":
        res1 = rec(idx+1, idx, t-1) + 1
        res2 = rec(idx+1, cur, t+1)
    else:
        res1 = rec(idx+1, idx, t+1) + 1
        res2 = rec(idx+1, cur, t-1)

    res = min(res1, res2)
    dp[idx][cur][t] = res

    return res


ans = rec(0, 0, 0)
print(ans)

Submission Info

Judge Result