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
'PS > BOJ' 카테고리의 다른 글
| 백준 BOJ 20003 거스름돈이 싫어요 (0) | 2021.06.07 |
|---|---|
| 백준 BOJ 1027 고층 건물 (0) | 2021.06.07 |
| 백준 BOJ 1812 사탕 (0) | 2021.06.03 |
| 백준 BOJ 17094 Serious Problem (0) | 2021.06.02 |
| 백준 BOJ 1781 (0) | 2021.05.24 |