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

https://www.acmicpc.net/problem/10799

 

해설

그림을 보고 이해를 하도록 하자.

흰색은 쇠막대기 빨간선은 레이져라고 하자. 쇠막대기의 개수는, 레이저가 발사 되었을 때, 쇠막대기의 개수만큼 잘린 쇠막대기의 개수가 늘어난다

위의 모습에서는 레이저를 기준으로 왼쪽으로 2개가 늘어난 모습이다.

코드를 보고 이해하도록 하자.

 

코드

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <stack>
#include <sstream>
#include <set>
#include <unordered_set>
#include <cmath>
using namespace std;
using ll = long long;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	stack<int> stk;
	string str;
	int cnt = 0;
	cin >> str;
	for (int i = 0; i < str.size(); ++i)
	{
		if (str[i] == '(' && str[i + 1] == ')') // 레이저라면
		{
			cnt += stk.size(); // 여태까지 쌓인 파이프 수만 큼 더한다
			i++;
		}
		else if (str[i] == '(') // 그냥 쇠막대기라면, 쇠막대기 개수를 늘린다.
		{
			stk.push(i);
		}
		else if (str[i] == ')') // 쇠막대기의 끝이라면, 1개만큼 개수를 늘린다.
		{
			cnt++;
			stk.pop();
		}
	}
	cout << cnt << endl;

	return 0;
}

 

후기

레이저를 기준으로 현재 쇠막대기의 개수만큼 잘린 쇠막대기의 개수가 늘어난다는 부분을 찾기가 힘든 문제였던거 같다.

이 부분만 찾을 수 있다면 풀 수 있는 문제라고 생각한다.