PS/BOJ
백준 BOJ 10422
JOFTWARE
2021. 5. 25. 16:06
https://www.acmicpc.net/problem/10422
10422번: 괄호
‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호
www.acmicpc.net
알고리즘 : DP, 카탈란 수
일단 홀수면 무조건 0
짝수면 dp를 사용.
dp[i]를 구할 때 i-2개의 괄호들은 이미 완성된 괄호들이라고 보고 가능한 모든 경우의 수를 찾아 더한다. dp[j]*dp[i-2-j]
찾아보니 카탈란 수라는 개념이었다.
728x90