BOJ 12874 괄호 문자열

"(" 와 ")" 로만 이루어진 문자열이 주어지면 그 문자열의 부분 문자열(연속될 필요 없음, 문자열에서 일부 문자를 지워서 만들 수 있는 문자열) 중에서 서로 다른 올바른 괄호 문자열의 개수를 구하는 문제이다.

백준님의 풀이를 봤다.

그래도 어렵다. 이해가 잘 안된다.
겨우겨우 이해한 것을 정리해 보겠다.

올바른 괄호 문자열을 찾긴 해야하는데, 그 중에서 중복되지 않는 즉 서로 다른 것들의 개수를 찾아야 한다.
()() 가 주어지면 여기서는 ()와 ()()로 2개이다.
일단 올바른 괄호 문자열의 최소 단위는 ()이고, 항상 "("와 ")"가 왼쪽 오른쪽에 같은 개수로 존재해야 한다. 즉, "("가 하나 있으면 ")"도 하나 있어야 한다.
어떤 것은 그리고 ()()()()나 (())(())처럼..올바른 문자열이 합쳐진 것도 올바른 문자열이다. 여튼 결국은 "("가 반드시 먼저 나와야하고, 그 이후에 같은 개수의 ")"가 필요하다.

먼저 가장 앞에 있는 "("를 찾는다. "("가 없을 때는 ")"가 아무리 많아도 의미 없는 문자열이다. "("를 찾았으면, 그 이후에 오는 가장 앞에 있는 "(", ")"을 둘 다 찾아본다.
만약 "("뒤에 ")"가 바로 오면 ()가 만들어져서 1개이다.
만약 "("뒤에 "("가 오면 뒤에 ")"가 2개 오기를 기다리게 된다. 이렇게 보면서 "("의 개수와 ")"의 개수가 같아지면 1개의 올바른 문자열을 만든 것이 된다.

"("나 ")"을 찾을 때, 가장 앞에 있는(가까운) 것부터 처리하고 계속해서 누적해가기 때문에 중복이 발생할 수 없다. ()가 한 번 만들어지면 그 이후로는 ()의 뒤에 덧붙여진 것이 만들어질 것이고 ((가 만들어지면 그 이후에도 ((뒤에 덧 붙여진 것이 만들어지므로 중복되지 않는다.

그리고 가장 앞에 있는(가까운) 것부터 처리하면서 뒤에 "("가 오는 경우, ")"가 오는 경우를 모두 보기 때문에 "("와 ")"를 최대한 많이 붙여볼 수 있어서, 즉 올바른 문자열은 뒤에 "("나 ")"가 오는 경우밖에 없고 가장 앞에 있는 것부터 처리해서 누적해 나감으로써 최대한 많이(모든 경우를) 보게 되어 모든 경우를 다 커버할 수 있다.

그래서 d[xth][open] = xth번째 문자를 볼 때(보기 시작할 때), 그 때까지 누적된 열린 괄호가 open개일 때의 서로 다른 올바른 부분 문자열의 개수.

d[xth][open] = d[next_open_xth][open+1] + d[next_close_xth][open-1]
(next_open_xth와 next_close_xth는 바로 다음에 오는 "(", ")" 의 위치)
그리고 open이 0이 되면 즉, "("와 ")"의 개수가 같아지면 count +1

구현해 보자.
구현하면서 dp구현의 편의를 위해 char str[102]로 놓고 str+1부터 채웠는데, char배열을 전역변수로 선언해놓으면 '\0' (NULL)로 초기화되는 것 같다. 그래서인지 답이 항상 0이 나왔다. 그래서 그냥 str[0]위치에 'x'를 채우고 했다.

출처 : BOJ 캠프 백준님 강의 자료 및 풀이