[백준 10799] 쇠막대기

문제 링크 : https://www.acmicpc.net/problem/10799

10799번: 쇠막대기

 

백준에 있는 예제를 통해 막대 개수를 세는 알고리즘을 짜 보자

 

확실한 것은 막대기를 자르는 레이저가

 

최종 막대의 개수를 결정하는 요소라는 것이다

---

레이저가 막대기를 관통하는 것은

 

하나의 막대기가 두개로 분할되는 것이 아니라

 

하나의 막대기의 일정 부분을 잘라서 새로운 막대기를 만들어내는 것이다

 

결국 똑같은 말이지만 관점을 다르게 해야 쉽게 막대의 개수를 셀 수 있는 방법이 보인다

---

 

먼저 모든 막대기가 준비되어 있고 (괄호의 입력에 따라서)

 

그 위에서 레이저가 왼쪽에서부터 하나씩 쏴진다고 생각해보자

 

기존에는 5개의 막대가 존재한다

 

첫번째 레이저는 아무 막대도 관통하지 않았으므로 막대의 개수는 변함 없다 (5개)

 

두번째 레이저는 세개의 막대를 관통했다

 

이 때문에 기존의 막대에서 (관통된 막대들) 새로운 막대가 생겼다 (3개)

 

그리고 기존의 막대들의 개수에는 변함이 없다 (5개)

 

총 8개의 막대가 존재하는 셈이다

 

세번째 레이저도 3개의 막대를 관통한다.

 

위와 마찬가지로 새로운 막대가 세개 생기고

 

기존의 막대들은 전부 유지되므로

 

총 11(8+3)개의 막대가 존재한다

 

4, 5, 6번째 레이저도 마찬가지다

 

4번째 레이저는 새로운 3개의 막대 (3개의 막대를 지나치므로)

 

5번째 레이저는 새로운 2개의 막대 (2개의 막대를 지나치므로)

 

6번째 레이저는 새로운 1개의 막대 (1개의 막대를 지나치므로)

 

를 추가한다.

 

총 17개

 

여기서 중요하게 봐야될 점은 기존의 다섯개의 막대가 부분적으로 잘려나가서

 

짧아졌지만 사라지지않고 그대로 존재한다는 것이다

---

결국 레이저에 의해 잘린 막대기의 개수는

 

(각 레이저가 자른 막대의 개수의 총합) + (기존 막대의 개수)

---

이제 코드로 구현만 하면 된다

 

순서대로 괄호를 보면서 레이저를 만났을 때 쌓인 막대의 개수만큼 결과에 더해준다

 

쌓인 막대의 개수는 스택을 이용하여 계산하였다

 

(구체적으로는 스택의 크기를 의미하는 cnt 변수)

 

열린괄호가 등장하면 새로운 막대의 시작 ( cnt++ )

 

닫힌 괄호가 등작하면 막대 하나가 끝남 ( cnt-- )

 

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

int main(void) {
	string str;
	cin >> str;	// 문자열 입력

	int sum = 0;  // 총 막대의 개수
	int cnt = 0;
	int prev = 0;	// 만약 전에 열린괄호였으면 1, 닫힌괄호였으면 0
	for (int i = 0; i < str.size(); i++) {
		if (str[i] == '(') {	// 열린 괄호 등장
			cnt++;	// 새로운 막대가 하나 깔림
			prev = 1; // 다음 반복문에서는 전 괄호가 열린 괄호이다
		}
		else {	// 닫힌 괄호 등장
			if (prev == 1) {	// 바로 전이 열린괄호라는 것은 레이저라는 뜻
				cnt--;	// 레이저가 자르는 막대의 수는 cnt에서 1 빼야됨, 전에 레이저인 (에서도 ++해줬으므로
				sum += cnt;	// 레이저가 자르는 막대의 개수를 결과에 +=
			}
			else {	// 레이저가 아니라 그냥 막대의 끝
				sum++;	// 초기 막대들을 이런식으로 하나씩 세줌
				cnt--;	// 아래 깔린 막대가 하나 사라짐
			}
			prev = 0; // 다음 반복문에서는 전 괄호가 닫힌 괄호이다
		}
	}
	cout << sum << endl;	// 결과 출력

	return 0;
}