[EPPER/11회 9번]올바른 괄호 배열 구하기(중-2)

#include <iostream>
using namespace std;


/*
<모르겟음 ㅎ>


재귀함수로 계속해서 괄호를 생성해본다

괄호를 그릴때 -> 이 방향으로 그리고 항상 (가 먼저와야 하므로
괄호를 그릴때 "("부터 그리기 떄문에 
제한된 갯수 내에서 (는 얼마든지 계속해서 그릴수 있지만, 
ex.  (((( ) 뭐이런건 된다 그뒤에 )를 더그리면되니깐

그런데 )의 갯수는 제한이 된다. 
(를 막그렸을떈 )로 수습해서 하나의 괄호로 만들수 있지만 ))를 막그린 이상 (를 그려봣자 괄호가 완성안되니깐 
ex.  ()))))는 안된다 (를 추가해봤자 이미 틀린 괄호니깐 

=>결론을 말하면 괄호를 그려나갈 때, 

"("의 수보다 항상 ")"의 수가 많거나 같아야 한다. 



이를 지키면서 괄호를 재귀적으로 그려보면,

(이 0개, )이 0개 남으면? -> 종료 조건 1개

나머지의 경우,

1. 
(를 전부 사용함 앞부분을 어떻게 구성했든 (를 다 써버렸다면, 남은 방법은 )를 다써버리는 수밖에 없어서 -> 1개

2. "("의 수가 ")"보다 많은 경우 -> "(" 을 쓰든 ")"을 쓰든 규칙에 위반되지 않으므로 둘다 가능하다 

3. "("의 수와 ")"의 수가 같은 경우 -> ")"가 더 많아지는건 규칙에 위반 "("를 더사용해서 만들기만 가능 




*/
int solution(int right, int left){
	
	if(right == 0 && left == 0){
		return 1; //완성되었으니까 1추가됨 
	}
	else{
		if(left==0) return 1;
		else if(left<right) return solution(right-1,left) + solution(right,left-1);
		else if(left==right) return solution(right,left-1);
	}
	
}



int main() {
	char input[100];
	int n;
	cin >> n;
	//cout << "Hello Goorm! Your input is " << n << endl;
	
	cout<<solution(n,n)<<endl;
	return 0;
}