[BOJ_C++] 10799번: 쇠막대기

CODE

#include <bits/stdc++.h>
using namespace std;

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int sum = 0;
    string str;
    stack<int> pipe;

    cin >> str;
    for(int i=0; i<str.length(); i++){
        if(str[i] == '(') pipe.push(str[i]);
        else{
            pipe.pop();
            if(str[i-1] == '(') sum += pipe.size();
            else sum++;
        }
    }

    cout << sum;

    return 0;
}

문제 풀이

[문제 조건]
1. 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 '()'으로 표현된다. 또한, 모든 '()'는 반드시 레이저를 표현한다.
2. 쇠막대기의 왼쪽 끝은 여는 괄호 '('로, 오른쪽 끝은 닫힌 괄호 ')'로 표현된다.

예를 통해 어떤식으로 코드를 작성할 수 있을지 생각해보자.

 먼저 레이저가 나오면, 지금까지 자른 파이프의 개수를 더해줘야 한다. 이때 지금까지 자른 파이프의 개수는 왼쪽 괄호 '('와 같다고 볼 수 있다. 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않기 때문에 레이저가 지나가면 반드시 잘린 막대기가 생길 것이기 때문이다. 

 그렇다면 레이저는 어떻게 구분할 수 있을까? 레이저는 반드시 '()' 형식이기 때문에 바로 앞이 왼쪽 괄호 '('인지 확인하면 된다. 만약 오른쪽 괄호 ')'가 나온다면 그것은 쇠막대기의 끝이므로 +1을 하여 잘려나온 막대에 1개를 더해주면 된다.

결과