BOJ 10799. 쇠막대기

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

---

문제 요약

여러 쇠막대기가 겹쳐 놓여 있고, 위에서 수직으로 레이저를 쏘아 막대를 자른다. 배치는 괄호 문자열로 주어진다. 바로 붙은 ()는 레이저이고, 그 밖의 (와 )는 각각 막대의 왼쪽 끝과 오른쪽 끝이다. 막대는 자기보다 긴 막대 위에만 끝점이 겹치지 않게 놓이고, 막대마다 레이저가 적어도 하나 지나간다. 잘린 조각의 총 개수를 구한다.

---

1. 문제 해석

• 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( )’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현한다. • 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘ ) ’ 로 표현된다.

이 문제는 스택을 직접 사용해서 풀이를 해야한다. 가장 중요한 부분은 ‘인접하다‘는 것은 스택에 넣었을 때 ‘인덱스가 1만큼 차이 난다’ 는 것이다.

• 올바른 괄호 문자열과 비슷하게 풀 수 있다. • ()가 나올 때 마다 스택에 들어있는 (의 개수를 세어준다 • 그런데, )가 나왔을 때, 이것이 레이저인지 쇠막대기인지 구분을 해줘야 한다. • 레이저는 항상 ()와 같이 붙어진 상태로 나온다. • 스택에 (의 인덱스를 넣어서 인덱스가 1차이 나는지 확인해야 한다.

---

2. 문제 풀이

#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main() {
    string a;
    cin >> a;
    int n = a.size();
    stack<int> s;
    int ans = 0;
    for (int i=0; i<n; i++) {
        if (a[i] == '(') {	  // 여는 괄호면 스택에 넣음
            s.push(i);
        } else {	  	  // 닫는 괄호라면
            if (s.top()+1 == i) { // 인덱스가 1차이나면, 레이저이므로
                s.pop();	  // 스택에서 꺼내고
                ans += s.size();  // 스택크기만큼 잘라준다
            } else {		  // 인덱스가 1이상 차이나면, 쇠막대기 끝부분이므로
                s.pop();	  // 스택에서 꺼내고
                ans += 1;	  // 끝부분 잘린개수 추가
            }
        }
    }
    cout << ans << '\n';
    return 0;
}