Submission #3011788

---

Source Code Expand

S = input()

memo_dic = {}


def dfs(i, idx, cnt, t):
    if i == len(S) and t == 0:
        return idx + cnt
    if t < 0 or i == len(S) and t != 0:
        return 1000
    if (i, idx, cnt, t) in memo_dic:
        return memo_dic[(i, idx, cnt, t)]

    if S[i] == "(":
        res1 = dfs(i+1, i, cnt+1, t-1)
        res2 = dfs(i+1, idx, cnt, t+1)
    else:
        res1 = dfs(i+1, i, cnt+1, t+1)
        res2 = dfs(i+1, idx, cnt, t-1)

    res = min(res1, res2)
    memo_dic[(i, idx, cnt, t)] = res

    return res


ans = dfs(0, 0, 0, 0)
print(ans)

Submission Info

Judge Result