https://programmers.co.kr

문제:

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

풀이:

괄호를 () 라고 했을 때, 이것을 ( 따로 ) 따로 생각해서 순열을 구한다고 해보자.

이 때, 나열 할 수 있는 경우의 수는 (2*n)! 이 된다.

그러나 ( 의 갯수와 ) 의 갯수가 각각 n개씩 중복되므로 (n! * n!) 로 나눠주게 된다.

그리고 ()() 와 ())( 를 봣을 때 오른쪽 것은 틀린 것이므로 오른쪽 왼쪽을 같은 순열이라고 취급하여 n으로 한번 더 나눠준다면,

(2 * n) ! / (n! * n! * n) 이 답이 되게된다.

코드:

사용언어 : c++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    long long m1 = 1;
    for(int i = 2 * n; i > n; i--)
        m1 *= i;
    for(int i = 2; i <= n + 1; i++)
        m1 /= i;
    return m1;
}