문제 설명
올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 갯수를 반환하는 함수 solution을 완성해 주세요.
제한 사항
- 괄호 쌍의 개수 N : 1 ≤ n ≤ 14, N은 정수
풀이
문제를 요약하면, n개의 괄호쌍을 만들 때, 올바른 괄호쌍의 개수를 구해야 한다.
처음 이전 괄호쌍의 개수를 이용해 문제를 풀 수 있다고 생각이 들었다.
그래서 DP문제라고 생각은 했지만, 핵심 접근법에는 도달하지 못했다.
내가 처음 생각한 방법은, 이전 괄호쌍 중 ()가 연속으로 나오는 경우는 항상 1개이고, 나머지 괄호쌍의 사이에 새롭게 추가되는 ()를 하나씩 넣는다고 가정하면 점화식을 구할 수 있을 것이라 생각했다.
하지만, 이렇게 되면 겹치는 경우가 생긴다.
이를 점화식만으로는 판단할 수 없다고 생각했다.
즉, 이렇게 문제를 풀기 위해서는 직접 괄호쌍을 만들면서 문제를 풀어야 가능한 해결법이 된다.
물론, n이 14보다 작거나 같다는 제한 사항이 있기에 직접 만들어도 괜찮을 수 있다.
그래도 DP로 푸는것이 시간 복잡도에서 유리하다고 생각하여 진행하지 않았다.
이 문제의 핵심은 새로 추가되는 괄호쌍을 어디에 배치할 것인가이다.
새로 추가되는 괄호쌍안에 몇 개의 괄호쌍이 들어가는지를 통해 정답을 구할 수 있다.
새로 추가되는 괄호쌍안에 배치되지 않은 괄호쌍들은 밖에 배치된다.
즉, 기존에 알고 있던 올바른 괄호쌍의 개수를 통해 새로 추가되는 괄호쌍안에 몇 개가 들어가는지에 따라 만들 수 있는 경우의 수를 구할 수 있다.
예를 들어, n이 4인 상황을 생각해 보자.
그렇다면, 다음과 같은 경우의 수가 존재한다.
- 새로 추가되는 ()안에 아무것도 없는 경우: ()((())), ()(()()), ()(())(), ()()(()), ()()()() → dp[0] * dp[3]
- 새로 추가되는 ()안에 한 개의 괄호쌍이 있는 경우: (())(()), (())()() → dp[1] * dp[2]
- 새로 추가되는 ()안에 두 개의 괄호쌍이 있는 경우: ((()))(), (()())() → dp[2] * dp[1]
- 새로 추가되는 ()안에 세 개의 괄호쌍이 있는 경우: (((()))), ((()())), ((())()), (()(())), (()()()) → dp[3] * dp[0]
즉, n-1개까지의 괄호쌍을 안다면 n개의 괄호쌍의 경우의 수를 구할 수 있다.
아무것도 없는 경우는 사실 0가지이지만 경우의 수 계산을 위해 1로 설정해야 한다.
전체 코드
#include <string>
#include <vector>
using namespace std;
int solution(int n) {
vector<int> dp(n+1, 0);
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i++)
{
int temp = 0;
for(int j = 0; j < i; j++)
{
temp += dp[j] * dp[i-j-1];
}
dp[i] = temp;
}
return dp[n];
}