[프로그래머스] Level4 - 올바른 괄호의 갯수

> 문제

문제 : [올바른 괄호의 갯수]

> 문제풀이

올바른 괄호란 (()) 나 () 와 같이 올바르게 모두 닫힌 괄호를 의미한다.

괄호 쌍 n개가 주어질 때 만들 수 있는 모든 가능한 괄호의 갯수는 몇개인가 ?

1. 카탈란 수 ( Catalan number )

n-1쌍의 올바른 괄호에 ()를 알맞은 곳에 넣어주는 방법을 센다.

만약, (A)B 와 같이 넣는다고 하면, A와 B도 올바른 괄호가 성립해야 하며, A에 k쌍이 있다면 B에는 n-k-1쌍이 있어야 한다.

따라서 다음과 같은 점화식을 얻을 수 있다.

C1 = C0C0

C2 = C0C1 + C1C0

C3 = C0C2 + C1C1 + C2C0

…

카탈란 수열은 파스칼 행렬에서 (0,0), (2,1), (4,2) … 에서 얻어지는 수열(1, 2, 6, … )을 1,2,3 … 차례대로 나누면

1, 1, 2, 5, 14 … 수열을 얻는다. 이를 카탈란 수라고 하며, 2nCn * (1/n+1) 와 같은 일반항을 얻을 수 있다.

class Solution {
    public int solution(int n) {
      int[] dp = new int[n + 1];
      dp[0] = 1;
      dp[1] = 1;
      for (int i = 2; i <= n; i++) {
        for (int j = 0; j < i; j++) {
          dp[i] += dp[j] * dp[i - j - 1];
        }
      }
      return dp[n];
    }

}

2. 올바른 경우의 수 = 모든 경우의 수 - 올바르지 않은 경우의 수

2nCn - 2nCn+1

간소화하면, 2nCn / n+1

class Solution {
  static int c(int n, int r) {
		if (r == 0 || r == n) {
			return 1;
		} else {
			return c(n - 1, r - 1) + c(n - 1, r);
		}
	}

	public int solution(int n) {
    // return c(2*n, n) - c(2*n, n+1);
		return c(2 * n, n) / (n + 1);
	}
}

문제 출처 : Programmers