[BOJ] 3012번: ZAPIS

https://www.acmicpc.net/problem/3012

D[i][j]를 S[i:j]에서의 가능한 가짓수라고 할 때, sep = i+1, i+3, ... , 에 대해 D[i][j] = sigma( kind(S[i], S[sep])*D[i+1][sep]*D[sep+1][j] )라는 식을 얻을 수 있습니다. kind(a, b)는 a, b 두 문자로 만들 수 있는 쌍의 갯수인데, 예를 들어

kind( ? ? ) = 3

kind( ( ? ) = 1

kind( ( ) ) = 1

kind( { { ) = 0

입니다.

위의 점화식은 S[i]와 짝지어지는 괄호 쌍이 S[sep]이라고 간주했을 때의 경우의 수입니다.

문제에서 마지막 5자리를 출력하도록 하는 것이 처리가 굉장히 껄끄러웠습니다.

https://github.com/blisstoner/BOJ/blob/master/3032.cpp