N 개의 괄호쌍을 이용해서 만들 수 있는 괄호의 종류를 P(n) 이라 하면 P(n-1)의 각 케이스에 대해서

1) 앞에 ()를 붙인다 2) 뒤에 ()를 붙인다. 3) ( ... )으로 둘러싼다

의 세가지 경우가 있을 수 있습니다. 그런데 이 때 ()()() 과 같이 여닫는 괄호가 연속된 경우는 앞에 ()를 붙인 것과 뒤에 ()를 붙인 것이 같기 때문에 중복된 케이스로 봅니다.

따라서 P(n) = P(n-1) * 3 - 1 의 관계식을 얻습니다. 그리고 P(1) = 1 이네요.

def p(n):
  if n < 2:
     return 1
  return p(n-1) * 3 - 1

"""
Catalan number를 이용한 문제 해결
(0, 0)에서 (n, n)까지 격자점을 지나는 최단 거리의 경로 중에서 직선 y = x를 
넘지 않는 경우의 수
: y = x를 넘지 않음 ==> (), /\ are ok )(, \/ are ng.

Catalan Number, C(n) = (2n)! / {n!(n+1)!}
where, n int >= 0
"""

def factorial(n):
    rst = 1 if n==0 else n * factorial(n-1)
    return rst

def catNum(n):
    rst = int(factorial(2*n) / (factorial(n) * factorial(n+1)))
    return rst

def main():
    N = 5 # 괄호 쌍의 개수
    print(catNum(N))


if __name__=="__main__":
    main()

# catNum = 1, 2, 5, 14, 42, ... for N = 1, 2, 3, 4, 5, ...

고등학교 졸업하고 수학을 배운 일이 없어 카탈랑 수가 뭔지를 몰랐네요. mohenjo님 감사합니다.

+1, -1을 각각 n개만큼 나열하여, 시작점에서부터의 부분합이 음수가 되지 않는 경우의 수는 n+1번째 카탈랑 수 입니다.
'('를 +1, ')'를 -1로 치환하면 같은 문제이며 문제의 답이 카탈랑 수라는 것을 알 수 있습니다.
동시에 뒤크 단어의 개수, 혹은 이진순서트리의 개수이기도 합니다.

mohenjo님 풀이와 같이 카탈랑수의 생성 함수를 사용할 수 있으며
다른 방법으로 파스칼의 삼각형을 이용할 수도 있습니다.
저는 중복이 되지 않도록 파스칼의 삼각형을 그렸습니다.

만약 수능에 같은 문제가 나온다면
파스칼의 삼각형을 그린 후 왼쪽 절반을 떼어놓고 층층히 더해나가면 빠르게 답을 구할 수 있습니다.
n개의 (1,1)과 (1,-1) 벡터를 x-축 이하로 떨어지지 않게하며 (0,0)에서 (n,0)까지 연결하는 경우의 수 그림을
시계방향 90도 회전해보면, 파스칼의 삼각형 반쪽자리와 같다는 것을 알 수 있습니다.

# 파이썬


def case_number(t):
    n = [1]
    for u in range(2*t+1):  # 2t+1층만큼의 파스칼의 삼각형을 그립니다. (1, 3, 5, 7...)
        m = n[:]  # m은 파스칼의 삼각형의 1줄입니다.
        for v in range(len(m) - 1):
            n[v + 1] += m[v]
        n.append(1)
    return m[t] - m[t-1]  # 파스칼의 삼각형 가운데 값과 그 옆 값의 차입니다.


print(case_number(1))
print(case_number(2))
print(case_number(3))
print(case_number(4))
print(case_number(5))

만들 수 있는 괄호를 찾아 가는 문제는 현재 비어있는 자리에 ( 나 ) 를 넣었을 때 문제가 없는지를 판단 하는 문제 이다.

N = 1인 경우는 1개 밖에 없음으로 무시하고 넘어간다.

N > 1 인 케이스에 대해서는 괄호를 만드는 조건상 무조건 앞뒤에는 (,)가 각각 들어가야 됨으로 N * 2 - 2의 자리에 어떤 것을 넣을 수 있을까의 문제로 바꾸어 볼 수 있다.

남은 자리에 넣는 과정에 있어서 현재 입력된 닫힌괄호의 갯수는 열린 괄호의 갯수를 넘을 수가 없다.

스코어를 열린 괄호를 넣을 때마다 + 1을 하고, 닫힌 괄호를 넣을 때마다 -1하는 식으로 전개하면 현재 구성된 조합의 정합성을 판단 할 수 있다. 로직은 재귀프로그래밍을 이용하여 무작위로 넣어 보다가, 점수가 0보다 작아지는 점에서는 규칙을 어긋나기에 멈추어 닫힌괄호가 열린괄호보다 많아지는 것을 막는다. 조합의 맨마지막은 )가 옴으로, 무작위로 넣은 결과가 1이 아니면 1보다 큰경우는 열린괄호가 더 많은 경우가 되어 규칙에 맞지 않는 조합을 생성하게 된다.

이를 이용하여 아래와 같이 로직을 형성 할 수 있다.

def getAvailableCombination(currentCost,leftSLot):
    if currentCost <0: return 0
    if leftSLot == 0 and currentCost ==1 : return 1
    elif leftSLot == 0 and currentCost != 1 : return 0
    return getAvailableCombination(currentCost + 1, leftSLot -1) + getAvailableCombination(currentCost - 1, leftSLot -1)

N = 3
if N == 1: print(1)
else: print(getAvailableCombination(1,N * 2 -2 ))

def parentheses(n):
    if n == 1 or n == 0:
        return 1
    else:
        result = 0
        for i in range(n):
            result += parentheses(i) * parentheses(n-1-i)
        return result


print(parentheses(int(input())))

Ruby

위키 카탈랑 수 참고함.

def cnt_valid_parenthesis(n)
  fact = ->(n) { n == 0 ? 1 : (1..n).reduce(:*) }
  fact[2*n] / (fact[n] * fact[n+1])
end

Test

cases, right_cnts = [1, 2, 3, 4, 5], [1, 2, 5, 14, 42]
expect(cases.map(&method(:cnt_valid_parenthesis))).to eq right_cnts

def f(a,b):
    if b == 0:
        return(1)
    if a-1 >= b:
        return(f(a-1,b)+f(a,b-1))
    else:
        return(f(a,b-1))
N=int(input('괄호 쌍의 개수는?:'))
print('올바른 괄호의 개수는 %d개 이다.'%f(N,N))
# 주의: 겁나느림

괄호가 () 뿐만이 아니라 {} [] 도 포함이라면....? 다른 문자들도 섞여있다면...?

def jhyuk(data):
    exp = [x for x in data if x in ['[', ']', '(', ')', '{', '}']]
    j = 0
    while exp:
        k = 0
        for i in range(len(exp)-1):
            if exp[i:i+2] == ['(', ')'] or exp[i:i+2] == ['[', ']'] or exp[i:i+2] == ['{', '}']:
                exp[i:i+2] = []
                k += 1
                j += 1
        if k == 0: break
    if exp: return j
    else: return j

print(jhyuk('()AKJSDHK}{}{()}{)({|}{P{()(}_})}'))

def noc_tri(N):
    noc = []
    for i in range(N+1):
        for j in range(N+1):
            if i>j: noc.append(0)
            elif i==0: noc.append(1)
            else: noc.append(noc[-1]+noc[-N-1])
    return noc

N = int(input('괄호쌍 개수 N: '))
noc_bracket_set = noc_tri(N)
for i in reversed(range(N+1)):
    for j in range(N+1):
        print('{:>5}'.format(str(noc_bracket_set[(N+1)*i+j])),end='')
    print()
print('\n올바른 괄호쌍 경우의 수: {}'.format(noc_bracket_set[-1]))

괄호쌍 개수 N: 5
    0    0    0    0    0   42
    0    0    0    0   14   42
    0    0    0    5   14   28
    0    0    2    5    9   14
    0    1    2    3    4    5
    1    1    1    1    1    1

올바른 괄호쌍 경우의 수: 42

컨닝했음..

def P(n):
    return 1 if n == 1 else P(n-1) * 3 - 1

package pac;
import java.util.*;

public class franklin {

    public static void main(String args[])
    {   
        Scanner scanf = new Scanner(System.in);

        int get = 1;
        int number=0;
        System.out.print("수를 입력하시오: ");
        number = scanf.nextInt();

        for(int i = 0 ; i < number ; i++)
        {
            get = (2 * get) * (2 * i + 1) / (i + 2);
        }

        System.out.print("답: " + get);  
    }
}

N = int(input())

def right_pair(n):
    if n == 1:
        return 1
    return right_pair(n-1) * 3 - 1

print(right_pair(N))

from math import factorial as fac
def P3(n):
    return fac(2*n)//(fac(n)*fac(n+1))

import re
def bracket_balance() :
    s= input("괄호입력")
    s=re.sub("[^\(\)]","",s)
    o_cnt=0
    c_cnt=0
    for i in range(0, len(s)) :
        #닫는 괄호가 더 많아지면 false
        if o_cnt<c_cnt :
            return False
        elif s[i]=="(" :
            o_cnt+=1
            continue
        elif s[i]==")" :
            c_cnt+=1
            continue
    if o_cnt==0 and c_cnt==0 :
            raise ValueError
    return o_cnt==c_cnt

Python 3.7

a = int(input())
b = 1
for i in range(a+2, 2*a+1): b *= i
for i in range(1, a+1): b = b//i
print(b)

public class 올바른괄호의개수 {

    public static void main(String[] args) {

        Scanner scan =  new Scanner(System.in);
        int N = scan.nextInt();
        if(N==1) {
            System.out.println(1);
        }
        else {
            int A = 1;
            int x = 2*N;
            for(int i = 0; i<N; i++) {
                A=A*(x-i);
                A=A/(N-i);
            }
            A=A/(N+1);
            System.out.println(A);
        }
    }
}

def fac(n):
    if n==1:
        return 1
    else:
        return n*fac(n-1)

def catalan(n):
    return int(fac((2*n))/(fac(n)*fac(n+1)))

n=int(input("숫자를 입력하십시오: "))
print(catalan(n))

from copy import deepcopy
from collections import deque

def sol(inp) :
    res = deque([['(', 1]])
    while len(res[0][0]) < inp*2 :
        lst = res.popleft()
        if lst in res : continue
        else :
            if lst[1] == inp :
                res.append([deepcopy(lst[0])+')', deepcopy(lst[1])-1])
            elif lst[1] < inp and lst[1] > 0 :
                res.append([deepcopy(lst[0])+')', deepcopy(lst[1])-1])
                if lst[0].count('(') < inp :
                    res.append([deepcopy(lst[0])+'(', deepcopy(lst[1])+1])
            elif lst[1] == 0 :
                res.append([deepcopy(lst[0])+'(', deepcopy(lst[1])+1])
    return len(res), [i[0] for i in res]
if __name__ == "__main__" :
    print(sol(1))
    print(sol(2))
    print(sol(3))

결과

(1, ['()'])
(2, ['()()', '(())'])
(5, ['()()()', '()(())', '(())()', '(()())', '((()))'])

def Gwalho(x):
  n, log, logs = x, '', []
  oper(x, n, log, logs)
  print('N = ', x, ' : ',', '.join(logs),'  ', len(logs), ' 개')

def oper(num, depth, log, logs):
  if num == 1 and depth == 0:
      logs.append(log+')'); return
  if depth>0:
    log+='('; oper(num, depth-1, log, logs); log=log[:-1]
  if (depth<num and num>0):
    log+=')'; oper(num-1, depth, log, logs); log=log[:-1]


Gwalho(5)
#출력: N =  5  :  ((((())))), (((()()))), (((())())), (((()))()), (((())))(), ((()(()))), ((()()())), ((()())()), ((()()))(), ((())(())), ((())()()), ((())())(), ((()))(()), ((()))()(), (()((()))), (()(()())), (()(())()), (()(()))(), (()()(())), (()()()()), (()()())(), (()())(()), (()())()(), (())((())), (())(()()), (())(())(), (())()(()), (())()()(), ()(((()))), ()((()())), ()((())()), ()((()))(), ()(()(())), ()(()()()), ()(()())(), ()(())(()), ()(())()(), ()()((())), ()()(()()), ()()(())(), ()()()(()), ()()()()()    42  개