[프로그래머스(Programmers)][자바(java)] (Lv4) 올바른 괄호의 개수

 

https://programmers.co.kr/learn/courses/30/lessons/12929

코딩테스트 연습 - 올바른 괄호의 갯수

 

문제 풀이

 

public class Solution {
	
	int[][] dp;
	
	int bino(int n, int k) {
		if (k == 0 || k == n || n == 0)
			return 1;
		if (dp[n][k] != 0)
			return dp[n][k];
		return dp[n][k] = (bino(n - 1, k - 1) + bino(n - 1, k));
	}

	public int solution(int n) {
		int m = 2 * n;
		dp = new int[m + 1][n + 1];
		return bino(m, n) - bino(m, n - 1);
	}
}

 

n	괄호들	result
2	(()) ()()	2
3	((())) (()()) (())() ()(()) ()()()	5
4	(((()))) ((()())) ((())()) ((()))() (()(())) (()()()) (()())() (())(()) (())()() ()((())) ()(()()) ()(())() ()()(()) ()()()()	14
5	...	42
6	...	132

 

이 규칙은 카탈랑 수( ⊂ 이항 계수 )와 같다

• 이항 계수 ( Binomial Coefficient )  : 
  이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수
  ( n 개 중 r 개를 순서 없이 고르는 경우의 수 )
  
• 카탈란 수 ( Catalan number )  : 
  이진 트리의 수 따위를 셀 때 등장하는 수열
  ( 2n 개 중 n 개를 순서 없이 고르는 경우의 수 ) - ( 2n 개 중 n-1 개를 순서 없이 고르는 경우의 수)

이항 계수

카탈란 수