[BOJ] 하이터치☆메모리

하이터치☆메모리

TimeLimit	MemoryLimit	Condition	TAG
2s	1024MB	(1 ≤ A, B ≤ 2’000’000)	Implementation

그냥 고능하게 개수 세보면 정답이다.

왼쪽에 있는 A인 경우 왼쪽 열려있는 것보다 오른쪽이 열려있는 상황이 생기면 무조건 필요없는 상황이 생긴다. 왜냐하면 애초에 올바른 괄호가 아니기 때문에 볼 필요도 없다.

이와 같은 논리로 B에도 적용하여 stacked을 이용해서 현재 열려있는 괄호가 있으면 안 보도록 만들고, 아니면 이어 붙여졌을 때의 개수를 더해서 구한다.

문제 자체는 어려운 문제는 아닌데 이게 왜 골드인 느낌이 좀 강하다. 하지만 뭐 조합론 붙어있는걸로 봐서는 수학으로 뭔가 할 수 있을 것 같은데, 현재 내 풀이도 O(N)이여서 그냥 이대로 끝내려고 한다.

정답 코드

#include <iostream>
#include <queue>
#include <set>
#include <algorithm>
#include <random>

#define mod 1000000007LL
#define MAX 1'000'000LL
using namespace std;
using ll = long long;

ll counts[200'001];

int main(){
    
    string A, B;
    
    cin >> A;
    cin >> B;
    ll result = 0;
    ll left_open = 0, right_open = 0;
    ll stacked = 0;
    for(int i = 0; i < A.size(); i++){
        if(A[i] == ')') left_open ++;
        else right_open ++;
        if(right_open - left_open < 0) break;
        counts[right_open - left_open]++;
    }
    
    
    left_open = 0;
    right_open = 0;
    
    for(int i = 0; i < B.size(); i++){
        if(B[i] == ')'){
            left_open ++;
            if(stacked > 0) {
                right_open++;
                stacked--;
            }
        }
        else{
            // right_open ++;
            stacked ++;
        }
        
        if(left_open - right_open < 0 || stacked) continue;
//        cout << left_open << " " << right_open << " " << left_open - right_open << counts[left_open - right_open] << "\n";
        result += counts[left_open - right_open];
    }
    cout << result;
    
    return 0;
}