백준 10799 쇠막대기

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

#include <iostream>
#include <stack>

using namespace std;

int main() {


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

    string inp;

    cin >> inp;

    stack<char> s;
    int ans = 0;

    for (int i = 0; i < inp.size(); i++) {

        if (inp[i] == '(') {
            s.push(inp[i]);
        } else if (inp[i] == ')') {
            if (inp[i - 1] == '(') {
                s.pop();
                ans += s.size();
            } else {
                s.pop();
                ans++;
            }
        }

    }

    cout << ans;

    return 0;
}

 

1. 문제

여러 개의 쇠막대기를 레이저로 전달한다. 이 위치가 주어지는 데, 다음의 규칙을 따른다.

• 레이저는 ()으로 표현된다. 모든 레이저는 ()이다
• 쇠막대기는 위의 경우가 아닌 '(' 와 ')'로 표현된다

위의 그림과 같이 레이저로 쇠막대기를 절단했을 때, 잘리고 난 후 쇠막대기의 총 개수를 구하는 문제이다.

2. 풀이

(로 열리고 )로 닫히는 경우를 확인하는 스택 문제이다. 여기서 레이저의 여부를 확인하여 처리하면 된다.

 for (int i = 0; i < inp.size(); i++) {

        if (inp[i] == '(') {
            s.push(inp[i]);
        } else if (inp[i] == ')') {
            if (inp[i - 1] == '(') {
                s.pop();
                ans += s.size();
            } else {
                s.pop();
                ans++;
            }
        }

    }

쇠막대기와 레이저 두 경우 모두 '('일 경우 스택에 넣어준다. 뺄 때 확인하는데,

1. 레이저일 경우(문제 조건: 모든 '( )'는 반드시 레이저를 표현한다) 직전에  '('였을 것이다. 이 경우 레이저 분량의 (를 스택에서 pop하면 스택에는 쇠막대기의 왼편만 남는다. 쇠막대기를 자르면 해당 위치에 있는 쇠막대기의 개수가 두 배가 되므로 스택의 크기를 쇠막대기에 더하여 잘린 쇠막대기의 왼편 분량을 더한다.
2. 쇠막대기일 경우 해당 쇠막대기가 끝나는 지점이므로 해당 쇠막대기를 더한다.

위 연산의 결과를 출력하면 정답을 구할 수 있다.