풀고나니 단순한 DP

문제 : https://www.acmicpc.net/problem/12874
코드 : https://github.com/tktj12/cpp-problem-solving/blob/main/BOJ-12874/solution1.cpp

점화식 | Recurrence Relation

---

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

$pos$ : 현재 위치(인덱스)
$open$ : 현재까지 닫히지 않은 open bracket 개수
$next\_open\_pos$ : 다음 open bracket 위치
$next\_close\_pos$ : 다음 close bracket 위치

풀이 | Solution

---

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

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

$open == 0$일 땐 당연히 open bracket인 '('을 선택해야 한다. 그 다음부터는 '('을 선택할지 ')'을 선택할지 고르면 된다. 그러다 $open$이 다시 0이 되면 올바른 괄호 문자열 하나가 완성된 것이다.

참고 | Reference

---

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