[ SWEA 5432 ] 쇠막대기 자르기 (C++)

SWExpertAcademy의 쇠막대기 자르기(5432 / D4) 문제이다.

[ 문제풀이 ]

단순해 보이는데 생각을 좀 많이 해봐야 했던 문제였던 것 같다.

먼저, 쇠막대기들이 언제 조각이 나고, 그 조각을 어떻게 더해줘야 하는지 부터 생각을 해보자.

쇠막대기들은 2가지 경우에 조각이 난다고 볼 수 있다.

첫 번째 경우는 '레이저에 의해서 쇠막대기가 잘려질 때'

두 번째 경우는 '쇠막대기가 끝날 때'

위와 같은 상황으로 한번 알아보자.

먼저 레이저 'a'에 의해서 1, 2, 3번 쇠막대기 모두 조각이 나게 된다.

즉, a레이저 이전까지는 조각난 쇠막대기의 갯수가 0개 였지만, 'a'레이저에 의해서 쇠막대기의 조각이 3조각이 발생한다고

볼 수 있다.

'b'레이저에 의해서도 쇠막대기 조각들이 총 3조각이 발생하게 된다.

그럼 'c'레이저에 의해서는 몇 조각이 발생하게 될까 ??

'c'레이저는 1번 쇠막대기에는 영향을 미치지 못하게 된다. 왜냐하면 1번 쇠막대기가 이미 끝나버렸기 때문이다.

즉, 위에서 말했던 첫번째 경우인 "레이저에 의해서 쇠막대기가 잘라지는 경우" 에는 "현재 존재하는 쇠막대기의 갯수만큼

조각이 + 된다" 라고 생각할 수 있다.

이 경우 외에도 두번째 경우인 "쇠막대기가 끝나는 순간" 에도 조각이 추가된다.

1번 쇠막대기가 끝나는 시점을 한번 보게되면, 쇠막대기가 끝나는 것 만으로도 하나의 조각이 추가된다고 볼 수 있다.

따라서, 이 2가지의 경우들을 생각하면서 조각을 더해주면 된다.

[ 소스코드 ]

#include<iostream>
#include<string>
 
#define endl "\n"
using namespace std;
 
int Answer;
string S;
 
void Initialize()
{
    Answer = 0;
}
 
void Input()
{
    cin >> S;
}
 
void Solution()
{
    int Open = 0;
    for (int i = 0; i < S.length(); i++)
    {
        if (S[i] == '(') Open++;
        else
        {
            if (S[i - 1] == '(')
            {
                Open--;
                if (Open > 0) Answer = Answer + Open;
            }
            else
            {
                Answer = Answer + 1;
                Open--;
            }
        }
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}