10799번: 쇠막대기

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

10799번: 쇠막대기

입력 자체는 '(' 또는 ')'으로만 이루어져 있지만, 레이저가 쇠막대의 끝점과 겹치지 않으므로 '(' 직후 ')'가 나오는 경우는 따로 떼어놓고 생각해야 한다.

'('가 들어오는 경우 막대가 하나 추가된 것이고, '(' 직후 ')'가 들어온 경우 이전 문자인 '('는 막대를 추가한 것이 아니므로 막대 수를 1 줄인 뒤 토막의 개수를 막대의 개수만큼 늘리면 된다. 마지막으로 위 두 가지에 해당하지 않는, 즉 ')' 직후 ')'가 들어온 경우 막대 하나가 끝난 것이므로 막대 수를 1 줄이고 토막 수를 1 늘리면 된다. 이 과정을 괄호 문자열의 모든 문자에 대해 시행하면 정답을 얻을 수 있다.

#include <cstdio>

#define MAX 100000

int main() {
    // 입력받을 괄호 문자열
    char str[MAX + 1] = "";
    // d: 자를 쇠막대기의 개수, ans: 만든 토막의 개수
    int d = 0, ans = 0;

    // 괄호 문자열을 입력받은 뒤
    scanf("%s", str);
    // 괄호 문자열의 모든 문자에 대해
    for (int i = 0; str[i]; i++) {
        // 현재 문자가 여는 괄호라면 막대 하나를 추가한 것이므로 막대 수를 1 늘린다
        if (str[i] == '(') d++;
        // 현재 문자가 닫는 괄호고 이전 문자가 여는 괄호라면
        // 이전 문자가 쇠막대를 추가하는 문자가 아니므로 막대 수를 1 줄이고
        // 막대를 잘랐으므로 토막 수를 막대 수만큼 늘린다
        else if (str[i - 1] == '(') ans += --d;
        // 이전 문자와 그 이전 문자 모두 닫는 괄호라면 막대 하나가 끝난 것이므로
        // 막대 수를 1 줄이고 토막 수를 1 늘린다
        else { d -= 1; ans += 1; }
    }

    // 만든 토막의 개수를 출력
    printf("%d\n", ans);

    return 0;
}