[백준][10799] 쇠막대기

본 문제는 "(" 와 ")" 로 표현되는 쇠막대기의 수를 구하는 문제이다. 

 

이런 류의 문제를 풀 때면 종종 실수하는 것이 있다.

 

왜 그렇게 되는지 증명하려 한다는 것.

 

왜 "(", ")" 의 표현만으로 잘라진 쇠막대기의 수를 모두 나타낼 수 있는지를 생각한다는 점이다.

 

뭐 번쩍이는 두뇌로 1:1 매핑되는 것을 순간적으로 알아차릴 수 있다면 말리지 않겠지만, 

 

그냥 1:1 매핑이 된다고 가정하고 문제로 넘어가는 것이 상책이다.

 

그 가정 하에서 1:1 매핑되는 공식만 알아차리면 된다.

 

 

---

 

 

공식은 다음과 같다.

 

 

※ stack 부분 (state update) 

"( )" 이면, stack pass, "(" 이면, stack +1, ")" 이면, stack -1

 

※ calculate 부분  

"( )" 이면, stack size 만큼 cnt 증가, "(" 이면 calcuate pass, ")" 이면, cnt +1

 

 

 

---

 

 

이를 구현하면 다음과 같다.

 

스택은 STL deque로 구현하였다.

 

#include <iostream>
#include <deque>

using namespace std;

deque<int> st;

#define input_size 100000 + 1

char input[100000 + 1];


int main()
{
    int cnt = 0;
    cin >> input;    
    
    //cout << "input: " << input << endl;;
    
    for (int i=0; i<input_size-1 && input[i] != '\0'; )
    {
        //cout << "pos: " << i << endl;
        
        char cur = input[i];
        char next = input[i+1];
        
        // "( )" case
        if ((cur == '(') && (next == ')'))
        {
            // stack : pass
            
            // calculate
            cnt = cnt + st.size();
            
            i = i + 2;
        }
        
        // "(" case 
        if ((cur == '(') && (next != ')'))
        {
            // stack : +1
            st.push_back(1);
        
            // calculate : pass
            
            i = i + 1;
        }
        // ")" case
        if (cur == ')')
        {
            // stack : -1
            st.pop_back();
            
            // calculate :
            cnt = cnt + 1;
            
            i = i + 1;
        }
    }
    
    cout << cnt << endl;
}