레이팅 미적용설명
올바른 괄호 문자열이란 여는 괄호와 닫는 괄호로만 이루어져 있고 다음 조건을 만족하는 문자열이다:
- 빈 문자열은 올바른 괄호 문자열이다.
- \(A\)가 올바른 괄호 문자열이면 \((A)\), \([A]\), \(\{A\}\)도 올바른 괄호 문자열이다.
- \(A\)와 \(B\)가 올바른 괄호 문자열이면 \(AB\)도 올바른 괄호 문자열이다.
예를 들어 문자열 [({})], [](){}, [{}]()[{}]는 올바르지만, 문자열 [({{([, []({)}, [{}])([{}]는 올바르지 않다.
Ivica는 올바른 괄호 문자열이었을 것 같은 문자열을 발견했다. 문자 중 일부는 얼룩져서 읽을 수 없게 되었고, 어떤 문자였는지 알 수 없다.
읽을 수 없는 문자들을 괄호로 바꿔서 올바른 괄호 문자열을 만드는 방법의 수를 계산하는 프로그램을 작성하시오. 이 수는 매우 클 수 있으므로 마지막 \(5\)자리만 출력한다.
제약
입력 형식
첫째 줄에 문자열의 길이인 짝수 정수 \(N\) (\(2 \le N \le 200\))이 주어진다.
둘째 줄에 문자열이 주어진다. 읽을 수 없는 문자는 문자 ?로 표시된다.
출력 형식
그 문자열이 원래 나타낼 수 있었던 올바른 괄호 문자열의 개수를 출력한다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 60점 |
예제 1
입력
6
()()()출력
1예제 2
입력
10
(?([?)]?}?출력
3설명
The three matching regular bracket-sequences are ({([()])}), ()([()]{}) and ([([])]{}).
예제 3
입력
16
???[???????]????출력
92202문제 정보
태그