# 21653 Скобки

문제 : <https://www.acmicpc.net/problem/21653>

Скобки는 러시아어로 '괄호'라는 뜻.

#### 문제

여러분은 막 컴퓨터 과학 수업에서 산술 표현에 대해 배운 어린 프로그래머 아그네스를 만나게 됩니다. 아그네스는 산술 표현에서 괄호만 남기면 어떻게 될지 궁금해졌고, 검색을 통해 수학자들이 그러한 괄호 문자열을 '올바른 괄호 문자열'이라고 부른다는 사실을 알아냈습니다.

예를 들어, ()(())는 올바른 괄호 문자열입니다. 왜냐하면 (2+2):(3–(5–2)+4)와 같은 산술 표현에서 나올 수 있기 때문입니다. 반면에 (()와 ())(는 올바른 괄호 문자열이 아닙니다. 괄호가 정확히 6개(3개의 여는 괄호와 3개의 닫는 괄호)로 이루어진 올바른 괄호 문자열이 다섯 가지가 있다는 것도 쉽게 알 수 있습니다: ((())), (()()), (())(), ()(()) 그리고 ()()().

아그네스는 올바른 괄호 문자열을 변형하는 가장 간단한 방법에 흥미를 가졌습니다. 우선, 괄호를 추가하는 것에 집중하기로 했습니다. 아그네스는 괄호 하나를 추가하면 올바른 괄호 문자열이 아니게 된다는 것을 금방 알아냈지만, 두 개의 괄호를 추가하면 올바른 괄호 문자열로 남을 때도 있다는 것을 발견했습니다. 예를 들어, ()()에 두 개의 괄호를 여러 위치에 추가하면 (()()), (())(), ()(()), ()()()와 같은 올바른 괄호 문자열을 얻을 수 있습니다. 두 개의 괄호를 추가할 때 올바른 문자열로 유지하려면 하나의 여는 괄호와 하나의 닫는 괄호가 필요합니다.

아그네스는 주어진 올바른 괄호 문자열에 두 개의 괄호를 추가하여 다시 올바른 괄호 문자열이 되는 서로 다른 방법의 수를 계산하고 싶어졌습니다. 하지만 때때로 그 방법의 수가 매우 커질 수 있음을 알게 되었습니다. 아그네스는 추가된 괄호의 위치에 따라 서로 다른 방법을 구분합니다. 예를 들어, 간단한 괄호 문자열 ()에 두 개의 괄호를 추가하면 7가지 방법으로 올바른 괄호 문자열을 만들 수 있습니다: ()(), (()), (()), (()), (()), ()(), ()(). 여기서 추가된 괄호는 굵은 글씨로 표시되어 있습니다.

즉, 얻어진 괄호 문자열에서 여는 괄호가 위치한 인덱스 i와 닫는 괄호가 위치한 인덱스 j가 주어졌을 때, (i1, j1)과 (i2, j2)에 해당하는 두 방법은 i1≠i2 또는 j1≠j2인 경우 서로 다른 방법으로 간주됩니다.

이 문제에서는 주어진 올바른 괄호 문자열에 두 개의 괄호를 추가하여 다시 올바른 괄호 문자열이 되는 서로 다른 방법의 수를 계산하는 프로그램을 작성해야 합니다.

#### 풀이 과정

<figure><img src="/files/YQohjKlNNeG9UzDvWWo6" alt=""><figcaption></figcaption></figure>

경우의 수를 잘 따져보면 풀 수 있다.

괄호 안에 있는 곳에는 -0칸, -1칸씩 밀려있는 새로운 괄호쌍을 넣을 수 있![](/files/YbBcydMypxfstUmELpvO)고,

0칸, 1칸, ...  n칸씩 떨어져 있는 새로운 괄호쌍은 아무 칸에나 넣을 수 있다.

두 가지 괄호쌍 종류에 대한 경우의 수를 각각 계산해서 더하면 끝.

#### 정답 코드

```
bracket=input()
n=len(bracket)
stack=[]
res=0
cnt=0
for i in range(n):
    cnt+=1
    if stack and stack[-1]=='(' and bracket[i]==')':
        stack.pop()
    else:
        stack.append(bracket[i])        
    if not stack:
        res+=cnt*(cnt-1)/2
        cnt=0
res+=n*(n+1)/2+(n+1)
print(int(res))
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lazyartisan.gitbook.io/note/main-page/algorithm/undefined-1/21653-skobki.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.