풀고나니 단순한 DP

문제 : https://www.acmicpc.net/problem/12874

이 문제의 어려운 점이자 핵심은, 연속되는 부분이 아닌 순서만 상관있는 부분 집합인 것. 그리고 중복되는 경우는 고려하지 않는 것이라고 생각한다.

풀이

---

단순하게 생각하면, 특정 지점에서 다른 선택을 한 문자열들을 만든다면 중복되는 경우가 없을 것이다. 예를 들어 "( ( ) ( ) )"에서 두 부분 문자열 "( ( ) )", "( ) ( )"의 경우 2,3번째 문자를 다르게 선택하여 만든 것이다.

열려있는 괄호가 없을 땐 당연히 open bracket인 '('을 선택해야 한다. 그 다음부터는 '('을 선택할지 ')'을 선택할지 고르면 된다. 그러다 괄호 문자열 하나가 완성되면, 다시 open bracket을 선택해야 한다.

점화식 | Recurrence Relation

---

$DP(pos, open) = DP(next\_open\_pos, open+1) + DP(next\_close\_pos, open-1) + IsNewBS$

$pos$ : 현재 위치(인덱스)
$open$ : 현재까지 짝지어지지 않은 open bracket 개수
$next\_open\_pos$ : 다음 open bracket 위치
$next\_close\_pos$ : 다음 close bracket 위치
$IsNewBS$ : 중복되지 않는 괄호 문자열(Bracket String) 하나를 만들었다면 1, 아니라면 0

Code

---

https://github.com/tktj12/cpp-problem-solving/blob/main/BOJ-12874/solution1.cpp

Reference

---

https://fullalgorithmpanic.blogspot.com/2016/11/boj-12874.html