올바른 괄호의 갯수

---

출처 프로그래머스 - 올바른 괄호의 갯수

사용 언어 자바

문제 설명

올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 갯수를 반환하는 함수 solution을 완성해 주세요.

제한사항

괄호 쌍의 개수 N : 1 ≤ n ≤ 14, N은 정수

입출력 예

| n | result | | — | —— | | 2 | 2 | | 3 | 5 |

---

전형적인 카탈란…
그냥 카탈란 그 자체
Cn을 구하면 된다

• Cn = 2nCn - 2nCn-1
  • 2nCn = [(2n)! / {n! * n!}]
  • 2nCn-1 = [(2n)! / {(n-1)! * (n+1)!}]
    • [(2n)! / {(n-1)! * (n+1)!}] * {n(n+1) / n(n+1)}
    • = [(2n)! / {n! * n!}] * {n / (n+1)}
• = [(2n)! / {n! * n!}] - [(2n)! / {n! * n!}] * {n / (n+1)}
• = [(2n)! / {n! * n!}] * [1 - {n / (n+1)}]
  • [1 - {n / (n+1)}] = {(n+1) / (n+1)} - {n / (n+1)} = {1 / (n+1)}
• = [(2n)! / {n! * n!}] * {1 / (n+1)}
• = [(2n)! / {n! * (n+1)!}]

분자 (2n)!를 분모의 (n+1)!만큼 약분해버리고
분자 팩토리얼 값을 먼저 구한뒤
다음 줄에서 남은 분모(n!)만큼 나눠주었다

제출 답안

class Solution {
    public int solution(int n) {
        long answer = 1L;
        for (long i = n * 2; i > n + 1; i--) answer *= i;
        for (long i = n; i > 1; i--) answer /= i;
        return (int) answer;
    }
}