만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

보안 게이트

시간 제한5초메모리 제한1536 MB

요약
균형 잡힌 괄호 문자열의 한 구간을 뒤집고 일부 문자를 x로 바꾼 결과가 될 수 있는 서로 다른 문자열 S'의 개수를 구합니다.
난이도

보통10점 중 7점

유형
문자열, 동적 계획법, 완전 탐색
정답자
아직 제출이 없습니다

문제

Just Odd Inventions Co., Ltd.를 아시나요? 이 회사의 사업은 말 그대로 "기묘한 발명"을 하는 것입니다. 여기서는 줄여서 JOI 회사라고 부르겠습니다.

예제4

  1. 예제 1

    입력
    4
x))x
    예상 출력
    3

  2. 예제 2

    입력
    10
xx(xx()x(x
    예상 출력
    45

  3. 예제 3

    입력
    5
x))x(
    예상 출력
    0

  4. 예제 4

    입력
    10
xxxxxxxxxx
    예상 출력
    684