Topcoder SRM 714 Div1(Easy) Paranthesis Removal

\(2\leq{len}\leq{2500}\)

이 문제는 길이 len 의 correct parentheses sequence 가 주어졌을 때 왼쪽에 있는 '열린 괄호'를 하나와 임의의 위치에 있는

닫힌 괄호 하나, 총 두개를 지우는 행위를 빈 문자열이 될 때 까지 반복하는 방법의 수를 구하는데, 지울 때 마다 

지운 직후에도 correct paranthese sequence 이도록 지우는 방법의 수를 구하는 문제이다.

우선 이 문제를 좀 더 간단하게 바꿔보자. 왼쪽에서부터 열린괄호 하나와 닫힌괄호 하나를 지워나가는 것은 결국

열린괄호 하나와 닫힌괄호 하나를 매칭시키는 것과 같다고 볼 수가 있다. 물론 한 쌍을 지워도

correct parentheses sequence 이도록 말이다. 그럼 주어진 제약조건을 만족하면서 열린 괄호와 닫힌 괄호를

짝지어주는 경우의 수를 구하면된다. 어떻게 할까?

답을 가지고있을 ans 변수에 1을 할당하고

우선 왼쪽에서 부터 (의 개수 cnt를 세다가 )가 나오면 cnt를 ans에 곱해주자. 이것을 설명하자면 어떤 닫힌괄호 ')'는

자신보다 왼쪽에 있는 '(' 와만 짝지어질 수 있으며(자명하다), 이 중 어떤 하나와 짝지을 수 있으므로 cnt가지의

경우가 있으므로 cnt를 곱한 것이다. 그리고 ')'가 나왔을 때 ans를 갱신시켰다면 cnt를 1만큼 빼준다

왜냐하면 ')'가 나왔다는건 지금까지 나온 '(' 중에 임의의 하나와 짝지 지어졌을테니 어떤 것과 짝지어졌든 상관없이

짝지어질 수 있는 '(' 가 하나 줄어든 것은 확실하기 때문이다. 이 것을 문자열 s의 끝까지 반복해주면 답이나온다.

여기서 한가지 의문이 생길 수 있다. 과연 이렇게 했을 때 correct parenthesis sequence 가 아닌 경우가

생기지 않는다는 것이 보장되는가? 이다.

직접 parentheses sequence 를 한번 만들어보자. correct 하지 않는 순간은 왼쪽에 나온 '(' 보다 ')'가 많아지는 순간이다.

그 이외에는 무조건 correct 하다는 사실을 알 수가 있다. 그렇기 때문에 어떤 ')' 와 매칭을 시킬 '(' 를 선택하는데에 있어

단순히 이 ')' 보다 왼쪽에 있기만하면 된다는 사실을 할 수가 있다. 그러면 왼쪽에 나온 '('의 수를 세면서

앞에 나온 ')' 에 매칭되었을 '(' 의 수를 배제해 주면 선택가능한 '('의 수가 나오므로 계속 곱해나가면 답이나온다.

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
 
class ParenthesisRemoval {
    public:
    int countWays(string s) {
        long long ans = 1;
        int cnt = 0;
        for(int i = 0 ; i < s.size(); i++){
            if(s[i] == '(') cnt++;
            else {
                ans = (ans * cnt) % MOD;
                cnt--;
            }
        }
        return (int)ans;
    }
};