BOJ 30693 : Unusual competitions

• 문제 링크 : boj.kr/30693
• 난이도 : G5
• 태그 : 애드혹

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    string s;
    cin >> s;
    
    int sum = 0;
    int ans = 0;
    for(int i = 0; i < n; i++) {
        if(s[i] == ')') {
            if(sum <= 0) {
                ans++;
            }
            sum -= 1;
        }
        else {
            sum += 1;
        }
    }
    ans *= 2;
    if(sum != 0) ans = -1;
    cout << ans;
    return 0;
}

---

풀이

(와 )의 수가 같다면, 올바른 괄호 문자열이 아니게 되는 시점은 )가 (보다 많게 되는 시점이다.

(를 +1, )를 -1이라고 했을 때 합이 0이 되는 지점을 기준으로 문자열을 끊어보자.

이렇게 끊은 부분 문자열은 올바른 문자열 혹은 올바르지 않은 문자열이다. 또한 각각의 부분 문자열의 (와 )의 수는 동일하다.

올바른 문자열 구간은 재배열할 필요가 없다. 올바르지 않은 문자열만 재배열하면 된다. 따라서 답은 올바르지 않은 부분 문자열의 길이와 같다. 올바른 문자열의 끝은 )이고 올바르지 않은 문자열의 끝은 (이므로 두 구간을 섞어 해결하는 최적의 방법은 존재하지 않는다.

올바르지 않은 구간의 길이는 합이 음수가 되도록 하는 )의 수를 세고, 그 수에 2를 곱하면 된다.