[백준 10799] 쇠막대기 (C++)

풀이

이 문제는 그림을 그리면서 살펴봐야 쉽게 풀 수 있다.

아래 그림을 보면,

가장 위에 있는 숫자는 현재 막대기의 수를 의미한다.

아래의 숫자는 현재 레이저로 쐈을 때 절단되는 막대기의 수이다.

 

여는 괄호가 들어오면 stack에 push 한다.

닫는 괄호가 들어오면 다음과 같이 판단한다.

닫는 괄호 이전의 괄호가 여는 괄호였다면 pop을 하고 나서 정답에 +stack.size()를 해준다.

닫는 괄호 이전의 괄호가 여는 괄호가 아니라면 pop을 하고나서 정답에 +1을 해준다.

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main()
{
	string s;
	cin >> s;

	stack<char> st;
	int cnt = 0;
	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] == '(')
			st.push(s[i]);
		else
		{
			if (s[i - 1] == '(')
			{
				st.pop();
				cnt += st.size();
			}
			else
			{
				st.pop();
				cnt++;
			}
		}
	}

	cout << cnt << '\n';
	return 0;
}