[c++] 백준 #6531 이런 문제는 유치원생도 해결할 수 있어

< 풀이 >

분할정복 문제이다. 이때 중복해서 계산하는 게 있어서 시간초과를 피하기 위해서는 dp배열을 써주자. 

코드나 로직 자체는 최적화가 덜된 것 같지만.. 로직을 간단하게 설명하면,

{}으로 되어 있으면 set이고, {}안에 있는 것들이 ","를 기준으로 elem인지 확인을 해주면 된다.

 

 

< 소스코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

#define pb push_back
#define N_MAX 100010

string str;
int isElem(int a, int b);
int isSet(int a, int b);
vector<vector<int> > dp;

int isSet(int a, int b){
    // set은 brace로 연결되어 있는 것이 아니면 땡이다.
    int& ret = dp[a][b];
    if (ret != -1){
        return ret;
    }
    if (str[a] == '{' && str[b] == '}'){
        if (((a+2) == b) || ((a+1) == b)) return ret = 1; // 한개 혹은 빈 공집합
        if (isSet(a+1, b-1)) return ret = 1;
        // set이 아니면 elem인지 확인
        for(int i=a+1; i<=b-1;i++){
            if (str[i] == ','){
                if (isElem(a+1, i-1) && isElem(i+1, b-1)) return 1;
            }
        }
    }
    return ret = 0;
}

int isElem(int a, int b){
    int& ret = dp[a][b];
    if (ret != -1){
        return ret;
    }
    if (a > b) return ret = 0; // 범위 초과하는 경우
    if (a == b) return ret = 1; 
    else if (isSet(a, b)) return ret = 1; // set이 elem인 경우
    else {
        for(int i=a; i<=b;i++){
            if (str[i] == ','){
                if (isElem(a, i-1) && isElem(i+1, b)) return ret = 1;
            }
        }
    }
    return ret = 0;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T; cin >> T;
    for(int t=1; t<=T; t++){
        dp = vector<vector<int> >(210, vector<int>(210, -1));
        cin >> str;
        cout << "Word #" << t << ": ";
        int N = str.size();
        if (isSet(0, N-1) == 0) cout << "No ";
        cout << "Set\n";
    }

    return 0;
}