백준 10799번 쇠막대기 C++ 풀이

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

10799번: 쇠막대기

쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘리고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려진다. 
쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.

 

쇠막대기 문제는 괄호를 쇠막대기를 겹쳐놓은 모양으로 판단, 쇠막대기를 레이저로 절단하였을 시 잘려진 쇠막대기 조각의 총개수를 구하는 문제이다.

이미지 출처 : 백준 10799번 본문

문제의 포인트

자료구조를 활용하고, 레이저와 쇠막대기의 구분을 할 수 있는가?

문제 설명

쇠파이프와 레이저를 다른 개체로 보고 나눠야 한다.

(안에 괄호들) -> 쇠파이프

() -> 레이저

 

만약 레이저가  나오면, 여태까지 쌓여있던 파이프만큼 개수가 늘어난다.

그리고 파이프가 끝나면 파이프의 개수를 하나 줄이고, 총파이프의 개수를 하나 늘린다.

백준의 설명 이미지에 이해가 되도록 수를 추가함. 파란색은 겹쳐진 파이프 개수, 빨간색은 총 파이프의 개수

코드

#include<iostream>
#include<stack>
#include<string.h>
using namespace std;
int main()
{
	stack<int> s;
	string str;
	
	int cnt = 0;
	cin >> str;
	for (int i = 0; i < str.size(); i++)
	{
		if (str[i] == '(' && str[i+1] == ')')
		{
			cnt += s.size();
			i++;
		}
		else if (str[i] == '(')
		{
			s.push(i);
		}
		else if (str[i] == ')')
		{
			cnt++;
			s.pop();
		}
	}
	cout << cnt;
}

여담

문제를 푸는 보람을 굉장히 많이 느낀 문제이다. 만약 잘 풀리지 않는다면 노트를 펼쳐 팬으로 차근차근 그림을 그려보며 생각해볼 것을 권장한다.