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

오늘은 백준10799번 쇠막대기 문제를 풀어보도록 하자.

스택을 이용하여 풀 수도 있지만 그냥 그리디적으로 접근해도 된다. 코드는 간단하지만 그림을 꽤 짜ㅡ증나는 그림이다.

문제는 다음과 같다.

                               [접근법]

 1. '('가 나왔을 때는 막대기의 길이가 늘어난다는 것을 의미한다.
 
 2. ')' 또한 막대기의 길이가 늘어난다는 것을 의미하지만 그 전의 문자가 '('면 레이저라는 것을 의미한다.
 
 3. 따라서 ( ( or ) ) or ( ) or ) ( 의 모양이 나올 수 있고 현재 인덱스의 문자 전이 중요하다.
 
 4. ( ( or ) ) 일 때는 막대기의 길이를 1씩 증가시켜가면 되고, ( ) 일 때는 현재까지의 막대기의 값을 누적합하면 된다.
 
    또한 ) ( 일 때는 막대기가 끝나는 부분이므로 증가시켜준 1을 빼고 누적합하면 된다.

                                     [코드]
#include <iostream>
#include <string>
using namespace std;

int main() {
	string s, tmp = "";
	int stick = 0, result = 0;

	cin >> s;

	tmp = s[0];

	for (int i = 0; i < s.length(); i++) {
		if (s[i] == '(') {
			stick++;
		}
		else {
			stick--;

			if (tmp == "(") {
				result += stick;
			}
			else {
				result++;
			}
		}
		tmp = s[i];
	}
	cout << result << '\n';
}