[EPPER] 11회 9번

문제

 

---

풀이

 

재귀함수를 금방 떠올린다면 쉬울 문제이다. 여기서 가장 중요한 것은 오른쪽 괄호가 들어갈 조건이다. 왼쪽 괄호가 2개 나온 상태에서 오른쪽 괄호가 3개 들어갈 순 없다. 왼쪽 괄호는 몇개가 나와도 상관없지만, 오른쪽 괄호의 출현 가능 여부는 왼쪽 괄호의 수가 결정한다.

 

사용할 수 있는 왼쪽 괄호와 오른쪽 괄호는 각각 n개 이다. 우리의 목표는 총 2n개의 괄호를 전부 사용하는 것이다. 그러므로 일단 재귀를 끝내는 조건은 남은 왼쪽, 오른쪽 괄호의 수가 모두 0개여야 한다는 것이다. 그렇지 않은 경우에는 어떤 상황이 있을까?

 

1. 왼쪽 괄호를 전부 사용하고 오른쪽 괄호만 남은 상황 (left == 0)

2. 남은 왼쪽 괄호의 수가 남은 오른쪽 괄호의 수보다 적은 경우 (left < right)

3. 남은 왼쪽, 오른쪽 괄호의 수가 같은 경우 (left == right)

 

왼쪽 괄호가 오른쪽 괄호보다 많이 남아 있는 경우는 없다. 우리가 그런 상황이 일어나지 않도록 할 것이기 때문이다. 사실 오른쪽 괄호만 남은 상황에선 굳이 재귀함수를 호출할 필요 없이 바로 1을 리턴해도 상관없다. 해당 상황에서 가능한 경우는 남은 오른쪽 괄호를 연속으로 전부 사용하는 방법밖에 없으니까. 그러니까 재귀함수 종료 조건을

if(left == 0)
	return 1;

이렇게 해도 된다는 뜻이다.

 

아무튼 2번의 상황이라면 왼쪽 괄호, 오른쪽 괄호 어떤 것을 사용해도 상관없다. 3번의 상황이라면 왼쪽 괄호만 사용할 수 있다. 이를 고려해서 재귀함수를 완성한다.

---

소스코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int bracket(int left, int right) {
	if (left == 0 && right == 0) //둘 다 전부 쓴거면 1 반환
		return 1;
	else {
		if (left == 0) //왼쪽 괄호 다쓰면 오른쪽만 사용
			return bracket(left, right - 1);
		else if (left <= (right - 1)) //모든 상황에서 오른쪽 괄호가 왼쪽 괄호보다 많거나 같아야 짝 성립
			return bracket(left - 1, right) + bracket(left, right - 1);
		else //왼쪽 괄호와 오른쪽 괄호의 수가 같은 경우. 왼쪽을 쓰면 위에서 말한 균형이 깨지는 상황
			return bracket(left - 1, right);
	}
}

int main() {
	int n, cnt = 0;

	scanf("%d", &n);
	printf("%d", bracket(n, n));
}