[EPPER] 올바른 괄호 배열의 개수 구하기

양의 정수 n을 입력받아서 n쌍의 괄호로 만들 수 있는 올바른 괄호 배열의 개수를 구하는 프로그램을 작성하시오.

 

[입력 형식]

양의 정수 n을 입력한다(1<=n<=10)

 

[출력 형식]

n쌍으로 가능한 올바른 괄호 배열의 개수를 출력한다.

 

	예1	예2	예3
입력	1	2	3
출력	1	2	5

 

[풀이 방법]

재귀 호출을 이용하여 푸는 문제이다(카탈란 수를 이용해서도 풀 수 있다). 괄호 배열의 형식을 생각했을 때 올바른 괄호 배열의 경우 남아 있는 왼쪽 괄호의 개수가 남아 있는 오른쪽 괄호의 개수보다 항상 같거나 적어야 한다. 이 점을 생각해서 재귀호출을 이용한다.

import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		System.out.println(solution(n,n));
	}
	
	public static int solution(int left, int right) {
		if(left==0&&right==0) return 1; //왼쪽, 오른쪽 모두 사용
		else {
			//항상 left<=right여야 함
			if(left==0) {
				return 1; //왼쪽 괄호를 다 썼으므로 만들 수 있는 괄호 배열은 한종류(앞으로 다 오른쪽)
			}
			else if(right>left) return solution(left-1, right)+solution(left, right-1);
			else return solution(left-1, right);
		}
	}
}