[python] boj 10422 괄호

DP문제는 언제나 백준에 올라와 있는 난이도에 비해 상당히 어렵다. 진짜 아이디어가 생각 안 날라면 끝까지 안 나는거 같다. 그래서 여러 DP 문제를 풀어보고 여러 아이디어를 접해보는 것이 많은 도움이 된다.

그 중에서도 괄호와 관련된 아이디어는 두고두고 쓰일 것 같다는 생각이 들어 정리하려고 한다.

 

기본 아이디어

• 일단 괄호를 열고 닫으려면 짝수여야 한다.
• 위 그림에서 괄호 전체 개수를 n개로 잡고 첫 번째 연 괄호를 닫는 괄호가 i번째라고 한다.
• 첫 번째 연 괄호와 그 괄호를 닫는 사이의 공간(--------)의 괄호의 개수는 i - 2개가 된다.
• i번째 이후의 공간 이후(~~~~~~)의 괄호의 개수는 n - (i - 2) + 2라서 n - i 개가 된다.
• 괄호가 0개일 때는 아무것도 넣지 않는다는 차원에서 한 가지의 경우라고 할 수 있다.
• 결과적으로 dp[n] = dp[i - 2] * dp[n - i]라는 점화식이 만들어진다.

dp = [0 for _ in range(5001)]
dp[0] = 1

for n in range(2, 5001, 2):
    for i in range(2, n + 1, 2):
        dp[n] += dp[i - 2] * dp[n - i]
    dp[n] %= 1000000007

for _ in range(int(input())):
    print(dp[int(input())])

 

유의사항

• 카탈란 수라는 것과 관련이 있다고 하는데 지금의 나에겐 이해하기가 힘들었다.