프로그램 명: coci_zapis
제한시간: 1 초
정규 괄호 순열은 괄호들만으로 이루어져 있고 다음과 같은 조건들을 만족합니다.
- 빈 문자열은 정규 괄호 순열입니다.
- 만약 A가 정규 괄호 순열이면, (A), [A], {A} 또한 정규 괄호 순열입니다.
- 만약 A와 B가 정규 괄호 순열이면, AB도 정규 괄호 순열입니다.
예로, 순열 [({})], [](){}, [{}]()[{}]은 정규 괄호 순열이지만, [({{([, []({)}, [{}])([{}]은 아닙니다.
Ivica는 정규 괄호 순열로 보이는 문자열을 찾아냈으나, 몇몇 글자가 지워져 보이지 않습니다.
지워진 글자들에 괄호를 채워 만들 수 있는 정규 괄호 순열의 경우의 수를 구하세요. 경우의 수가 커질 수 있으므로 마지막 5자리만 출력하세요
A regular bracket-sequence is a string of characters consisting only of opening and closing brackets, and
satisfying the following conditions:
-
An empty string is a regular bracket-sequence.
-
If A is a regular bracket-sequence, then (A), [A] and {A} are also regular bracket-sequences.
-
If A and B are regular bracket-sequences, then AB is also a regular bracket-sequence.
For example, the sequences [({})], [](){} i [{}]()[{}] are regular, but the sequences [({{([, []({)} and
[{}])([{}] are not.
Ivica has found a string which looks like it could be a regular bracket-sequence. Some of the characters
have become smudged and illegible, and could have been any character.
Write a program that calculates how many ways the illegible characters in the string can be replaced by
brackets so that the result is a regular bracket-sequence. This number can be very large, so output only
its last 5 digits.
입력
The first line contains an even integer N (2 ≤ N ≤ 200), the length of the string.
The second line contains the string. Illegible characters are represented by the '?' character.
출력
Output the number of regular bracket-sequences the string could have read.
입출력 예
input
6
()()()
output
1
input
10
(?([?)]?}?
output
3
input
16
???[???????]????
output
92202
In the second example, the three matching regular bracket-sequences are ({([()])}), ()([()]{})
and ([([])]{}).
출처:coci 2007-2008 contest1
번역:Fate
[질/답]
[제출 현황]
[푼 후(0)]