[백준] 3012번 올바른 괄호 문자열 > 파이썬

백준 3012번 올바른 괄호 문자열 (난이도 : 中上)

출처 : 백준 3012번 올바른 괄호 문자열

---

나의 풀이 in Python3

# dp
# 범위 [시작, 끝]을 정해놓고 분할 탐색을 하며 적절한 쌍을 이루는지 파악
# 괄호가 명시된 경우 해당 괄호랑 쌍이지만 ?라면 모든 경우 대응가능
###########

n = int(input())
s = input()
cache = [[-1] * 201 for _ in range(201)]
op = "({["
cl = ")}]"

def f(start, end):
    if start > end: return 1

    if cache[start][end] != -1: return cache[start][end]

    ret = 0
    for i in range(start + 1, end + 1, 2):
    # 2 간격 : 그 사이에도 짝이 생겨야 함.
        for j in range(3):
            if s[start] == op[j] or s[start] == '?':
                if s[i] == cl[j] or s[i] == '?':
                    # start와 짝이 맞는 괄호 위치 i
                    # (start + 1) ~ (i - 1) 구간과 (i + 1) ~ end 구간을 분할 탐색해주며 쌍을 이루는지 파악
                    ret += f(start+1, i-1) * f(i+1, end)

    cache[start][end] = ret
    return ret

result = str(f(0, n-1))
print(result[-5:])

• 알고리즘 : 동적계획법(dp) 활용
• 괄호 경우의 수 : 3
• length 기준으로 앞 부분 : op - "({[" / 뒷 부분 : cl :")}]"
• dp 재귀함수 f(start, end) 설정

※ 코드에 대한 나머지 설명은 주석 참조