[백준/c++] 10799번: 쇠막대기

 

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

10799번: 쇠막대기

 

쇠막대기는 자신보다 긴 것 위에만 놓일 수 있다 - 끝점이 겹치면 안 됨

각 쇠막대기를 자르는 레이저는 적어도 하나 존재

레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않음

 

레이저 : ()

쇠막대기의 왼쪽 끝 : (

쇠막대기의 우측 끝 : )

 

→ ( 면 stack에 넣고, ) 면 stack에서 꺼낸다. 레이저 () 면 stack에 있는 쇠막대기( 개수만큼의 조각을 더해준다. 만약 )이라면 조각 개수를 하나씩 더해준다. 왜냐면 ) 면 쇠막대기가 stack에서 빠져나왔는데 자른 마지막 조각을 더해줘야 하기 때문!

 

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

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string s;
    int answer = 0;
    stack<char> st;
    cin >> s;
    
    for(int i=0; i<s.length(); i++){
        if(i+1 < s.length() && s[i] == '(' && s[i+1] == ')'){ //레이저
            if(!st.empty()) answer += st.size(); //안에 쇠막대기가 있다면
            i++;
        }else if(s[i] == '('){ //맨 위에 쇠막대기 넣기
            st.push(s[i]);
        }else if(s[i] == ')'){ //맨 위 쇠막대기 끝남
            st.pop();
            answer++; //나오면서 나머지 하나 추가
        }
    }
    cout << answer << '\n';
    return 0;
}

 

처음에 문제를 보고 덜컥 겁을 먹고 아.. 하지 말까 했는데ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

stack이라고 생각하고 또 풀어보니 쉽게 풀린 문제였다 크크