[BOJ]10422번 : 괄호

https://www.acmicpc.net/problem/10422

10422번: 괄호

 

분류 : 없음

 

import java.io.*;
import java.math.*;
import java.util.*;

class Myscanner {
    BufferedReader br;
    StringTokenizer st;

    public Myscanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }
}

public class Main {
    public static Myscanner sc = new Myscanner();
    public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static final long mod = 1000000007;

    public static void main(String[] args) throws IOException {
        int T = sc.nextInt();

        while (T-- > 0) {
            int N = sc.nextInt();
            if (N % 2 == 1) {
                out.println(0);
            } else {
                int ans = N / 2;
                BigInteger result = (Catalan(2 * ans, ans).divide(BigInteger.valueOf((ans + 1))));
                result = result.mod(BigInteger.valueOf(mod));
                out.println(result);
            }
        }
        out.flush();
    }

    private static BigInteger Catalan(int n, int k) {
        BigInteger res = BigInteger.ONE;

        if (k > n - k)
            k = n - k;

        for (int i = 0; i < k; ++i) {
            res = res.multiply(BigInteger.valueOf((n - i)));
            res = res.divide(BigInteger.valueOf((i + 1)));
        }
        return res;
    }
}

나머지 1000000007부터 불길한 문제...

길이가 홀수 일 경우에는 올바른 괄호 문자열이 될 수 없으므로 0 처리를 해주고

처음에는 2 -> 1, 4->2 이길래 2의 진수로 개수가 증가하나 싶어서 해봤는데 바로 틀렸다..

6개 째를 계산해보니 5개 , 8개 째는 14로 증가하길래 규칙을 못 찾고 계속 헤매다가 구글 검색을 해보니 카탈란 수 (Catalan Number) 라고 한다.. 살면서 처음 들어봤다.

카탈란 수를 계산 하는 재귀 코드로 구현하고 테스트로 N= 100을 집어넣어도 너무 오래 걸려 찾아보니 O(N) 만에 계산하는 법도 있었다.

 

참조 링크 : http://www.geeksforgeeks.org/program-nth-catalan-number/