26111: Parentheses Tree

• toc {:toc}

문제 확인하기

풀이

해당 문제는 ICPC Asia Regional - Seoul 2022 문제이다.

백준에서 어느 정도 접해본 괄호 문제이다. 괄호가 열림에 따라 depth가 증가하고, 괄호가 닫히면 depth, distance를 결과에 더해준다. 이 때, 유의할 점은 가장 깊은 부분에서 체크를 한 경우 해당 경로의 노드 점수는 체크하면 안된다는 점이다.

그림을 통해 확인해보자.
오른쪽 그림에서 4를 점수로 얻은 경우, 해당 경로의 depth 3, 2, 1은 점수를 체크하면 안 된다. 때문에 해당 조건을 찾아줘야 한다.

위에서 ( 가 나오는 경우 depth를 증가시키고 ) 가 나오는 경우 중, 연속으로 ) 가 나오는 경우에는 해당 depth에서의 계산을 마치고 다른 depth로 넘어가는 것임을 알 수 있다. 때문에 해당 부분은 결괏값에 넣으면 안 된다.

항상 범위 안에서 계산값이 성립하는지를 확인해야 하는데 쉽지 않다. 만약 ( 가 개 존재하고 ()가 개 존재하고 ) 가 개 존재한다면? depth가 만큼 증가하고 해당 distance 가 번 더해져야 한다. 때문에 결과값을 int로는 수용할 수 없다. long long int로 설정해줘야 한다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
 
int depth = 0;
long long res = 0;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    string str;
    cin >> str;
 
    for(int i = 0; i < str.size(); i++){
        if(str[i] == '('){
            depth++;
        }
        else if(depth != 0 && str[i] == ')' && str[i-1] != ')'){
            depth--;
            res += depth;
        }
        else depth--;
    }
 
    cout << res << endl;
    
    return 0;
}