3345번 - 괄호 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 174 | 55 | 40 | 32.258% |
문제
올바른 괄호 문자열을 다음과 같이 정의한다.
()와[]는 올바른 괄호 문자열이다.A가 올바른 괄호 문자열이라면,(A)와[A]도 올바른 괄호 문자열이다.A와B가 올바른 괄호 문자열이라면, 두 문자열을 이어 붙인AB도 올바른 괄호문자열이다.
적어도 한 쌍의 대괄호([와 그것에 대응하는 ])를 포함하고 있는 올바른 괄호 문자열이 있을 때, 모든 대괄호를 (로 바꾼 문자열을 부서진 괄호 문자열이라 한다.
예를 들어, ((와 ((((()))는 부서진 괄호 문자열이다. 첫 번째 문자열에서 올바른 괄호 문자열인 []를 얻을 수 있다. 두 번째 문자열은 다음과 같은 4가지 올바른 괄호 문자열을 얻을 수 있다. []((())), ([](())), (([]())), ((([]))).
부서진 괄호 문자열이 주어졌을 때, 여기서 얻을 수 있는 올바른 괄호 문자열의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 부서진 괄호 문자열의 길이 N(2 ≤ N ≤ 30000)이 주어진다. 둘째 줄에는 (와 )로 이루어진 길이가 N인 부서진 괄호 문자열이 주어진다.
출력
첫째 줄에 입력으로 주어진 부서진 괄호 문자열에서 얻을 수 있는 올바른 괄호 문자열의 개수를 1,000,000,009로 나눈 나머지를 출력한다.
예제 입력 1
4 ((()
예제 출력 1
2
[](), ([])
예제 입력 2
8 ((((((((
예제 출력 2
14
[][][][], [[]][][], [[]][[]], [][][[]], [[[]]][], [[][]][], [][[][]], [][[[]]], [[[[]]]], [[][[]]], [[[]][]], [[][][]], [[[][]]], [][[]][]
출처
Olympiad > Baltic Olympiad in Informatics > BOI 2012 1번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호