Baekjoon 10799 - 쇠막대기

💫 문제

---

🫧 Example Input/Output

// IN
// () : 레이저 (쇠막대기를 자를 수 있는)
// ( : 쇠막대기 시작 (왼쪽 끝)
// ) : 쇠막대기 끝 (오른쪽 끝)
()(((()())(())()))(())

// OUT
17 // 쇠막대기 조각 수

💫 C++ 풀이

---

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	string s;
	cin >> s;

	int pipeCount = 0;

	int score = 0;
	bool lastOpen = false;
	for (auto c : s)
	{
		if (c == '(')
		{
			score++;
			lastOpen = true;
		}
		else
		{
			score--;
			pipeCount += lastOpen ? score : 1;
			lastOpen = false;
		}
	}

	cout << pipeCount;
}

💫 Memo

---

1. 문자열에서 레이저 표시
   

2. 문자열에서 쇠막대기 표시
   

3. 레이저 지이잉
   

4. 레이저가 쇠막대기를 자르는 위치 표시
   • 닫는 괄호가 나올 때 쇠막대기가 잘리는 것을 확인할 수있다

5. 또 다른 정보를 표시, 여는 괄호라면 스택 +1, 닫는 괄호라면 스택 -1
   

6. 1~5번을 통해 규칙 찾기
   • 레이저에 포함된 닫는 괄호라면, 현재 스택만큼 쇠막대기가 잘린다
   • 쇠막대기에 포함된 닫는 괄호라면, 쇠막대기가 1번 잘린다
7. 코드로 옮기기
   • 전제 : 모든 문자열은 균형잡힌 괄호 문자열이다
     1. 각 문자에 대해 (for)
     2. 문자가 (면 점수 +1
     3. 문자가 )면
     • 일단 점수 -1
     • 만약 이전 문자가 (였다면 쇠막대기 += 현재 점수
     • 아니라면 쇠막대기 += 1

• 원래 스택을 써서 풀었는데, 어차피 균형잡힌 문자열이라 굳이 스택을 쓰지 않아도 된다.