앳코더90 - 002 - Encyclopedia of Parentheses（★3）

https://atcoder.jp/contests/typical90/tasks/typical90_b

002 - Encyclopedia of Parentheses（★3）

 

이녀석은 해석안하고 입력만 보고 풀었다.

 

N을 기준으로 브루트포싱해서 모든 경우의 수를 찾은 다음 백준에 있는 괄호 문제 처럼 확인해주면 시간안에 통과할 수 있다.

https://www.acmicpc.net/problem/9012

9012번: 괄호

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;

const int INF = 987654321;
const double pi = 3.14159265358979;
const int MOD = 1000000009;


vector<string> arr;
vector<char> v;
int N;

bool check(string s)
{
	stack<char> st;

	while (!st.empty())
	{
		st.pop();
	}
	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] == '(' )
			st.push(s[i]);
		else if (s[i] == ')')
		{
			if (st.size() != 0 && s[i] == ')')
			{
				st.pop();
			}
			else
			{
				return false;
			}
		}
	}

	if (st.empty())
		return true;
	else
		return false;
}

void dfs()
{
	if (v.size() == N)
	{
		string k = "";
		for (auto i : v)
		{
			k.push_back(i);
		}
		arr.push_back(k);
		return;
	}

	v.push_back('(');
	dfs();
	v.pop_back();
	v.push_back(')');
	dfs();
	v.pop_back();
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	dfs();

	vector<string> ans;
	for (auto i : arr)
	{
		if (check(i))
			ans.push_back(i);
	}
		

	sort(ans.begin(), ans.end());

	for (auto i : ans)
		cout << i << "\n";

	return 0;
}