올바른 괄호의 개수

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

카탈랑(또는 카탈란) 수이다.

f(n) = (2nCn) / (n+1)

import java.io.*;
import java.util.*;
 
public class Solution {
 
    static BufferedReader br;
    static BufferedWriter bw;
 
    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);
        }
    }
 
    static int solution(int n) {
        return c(2*n, n) / (n+1);
    }
 
    public static void main(String[] args) throws IOException  {
        // TODO Auto-generated method stub
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        System.out.println(solution(3));
    
        bw.write("\n");
        bw.flush();
        bw.close();
    }
}
 
class pair {
    int first, second;
    pair(int a, int b) {
        this.first = a;
        this.second = b;
    }
}
 
class tuple {
    int first, second, third;
    tuple(int a, int b, int c) {
        this.first = a;
        this.second = b;
        this.third = c;
    }
}
 
class PQ implements Comparable<PQ> {
    int first, second;
    
    PQ(int f, int s) {
        this.first = f;
        this.second = s;
    }
    
    public int compareTo(PQ p) {
        if(this.first < p.first) {
            return -1; // 오름차순
        }
        else if(this.first == p.first) {
            if(this.second < p.second) {
                return -1;
            }
        }
        
        return 1; 
        // 이미 this.first가 더 큰 것이 됐으므로, 1로 해준다.
        // -1로 하면 결과가 이상하게 출력됨.
    }
}