(c++)백준 10799번: 쇠막대기

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

10799번: 쇠막대기

[풀이]

레이저가 나오면 레이저에 의해 잘린 레이저 왼쪽의 조각의 수를 더해주는 방법을 사용하였다.

1. '('가 나오면 막대 수 +1

2. ')'가 나오면 레이저인지 아닌지 판별 후, 레이저이면 조각 수 더해주고, 아니면 막대가 끝났음을 표시

 

※주의할 점※

-'()'가 나오면 레이저 이므로 '('에서 막대 수 +1 한 것을 다시 빼주어야 한다.

-막대가 끝나면 막대 수에서 빼는 걸로 끝나는 게 아니라 끝난 막대 수 +1을 해 주어야 밑의 그림에 표시된 O부분을 더해줄 수 있다.

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

string str;

void solution() {
	cin >> str;
	int s = str.size();
	int stick = 0;
	int res = 0;
	int endStick = 0;//끝난 막대기

	for (int i = 0; i < s; i++) {
		//새로운 막대가 나오면
		if (str[i] == '(') {
			stick++;
		}

		if (str[i] == ')') {
			//레이저라면
			if (str[i - 1] == '(') {
				stick--;//직전에 센 건 막대가 아님
				res += (stick + endStick);//레이저에 의해 만들어진 조각 개수 더하기
				endStick = 0;
			}
			//막대가 끝난 거라면
			else {
				stick--;
				endStick++;
			}
		}
	}
	res += endStick;//마지막 레이저 오른쪽에 남은 조각 더하기
	cout << res << endl;
}

int main() {
	solution();
	return 0;
}