알약4811

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

완탐으로 해결해 보려고 하였으나 실패 역시나. 값이 너무 크다

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

public class Main {

    static int answer = 0;
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //w 개수는 h 개수와 동일함
        //w가 먼저 출현한 횟수가 h보다 많아야함 whh 불가능
        //n 개를 저장. n개의 카운트를 2(풀) 1(하프) 0(없음)

        while(true){
            int n = Integer.parseInt(br.readLine());
            if(n==0)
                break;

            int[] arr = new int[n*2];

            search(0, n*2, arr, 0, 0);

            System.out.println(answer);
            answer = 0;
        }

    }

    public static void search(int depth, int len, int[]arr, int onecnt, int zcnt){
        if(depth == len){

            answer++;
            //for(int i : arr)
            //    System.out.print(i + " ");
            //System.out.println();
            return;
        }

        for (int i = 0; i <= 1; i++) {

            //if(depth == len-1 && i == 1)
            //   continue;

            if(onecnt == len/2 && i == 1)
                continue;

            if(onecnt == zcnt && i == 0)
                continue;

            if(depth == 0 && i == 0)
                continue;

            arr[depth] = i;

            if(i == 1)
                search(depth+1, len, arr, onecnt+1, zcnt);
            else
                search(depth+1, len, arr, onecnt, zcnt+1);

        }
    }
}

어렵다
점화식을 봐도 왜 이렇게 되는것인지 이해되지 않는다

카탈란수 라고 검색해서 찾아봤는데 어렵다 하...

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

public class Main {

    static long[][] dp = new long[31][31];
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        dp[0][0] = 1;
        for (int i = 0; i <= 30; i++) {
            dp[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }
        while(true){
            int n = Integer.parseInt(br.readLine());
            if(n == 0) break;
            System.out.println(dp[n][n]);
        }
    }
}