코딩 테스트 - 올바른 괄호의 갯수

이것도 일단은 LV 4 

public class 올바른괄호의갯수_221217 {

    public static void main(String[] args) {

       

    }

   

    public int solution(int n) {

        //괄호 쌍의 개수 N : 1 ≤ n ≤ 14, N은 정수

        //[카탈란 수] 라는 걸 이용하면 간단하게(?) 풀 수 있음

                   

        int [] arr = new int[n+1];

       

        arr[0] = 1;

        arr[1] = 1;

       

        for(int i = 2; i <= n; i++){

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

                arr[i] += arr[i-j] * arr[j-1];

            }

        }

       

        System.out.println(arr[n]);

       

        return arr[n];

    }

}

이 문제 사실 저번에 푼 문제인데, 프로그래머스에도 나오는 것이었다.

(찐 코딩 테스트는 많이 안 본 편인데 탐색 쪽은 겁나게 나오는 것입니다 ★)

https://ckddn9496.tistory.com/16 <- 이 블로그에서 같이 

BigInteger 사용해서 풀어도 된다.

프로그래머스 다른 사람의 풀이에는 거의 BigInteger로 풀었음.

근데 사실상 long 타입 안 초과할 거 같은뎅!

(코딩 테스트는 약간 공부 같은 범주라서 깊이 생각 안 한 기준으로...?)

알고리즘은 뭔가 원시인이 고기를 익혀 먹는 것처럼 공부하고 있는데 약간 이런 느낌이다.

고기를 생으로 먹는다 -> 먹을 만 하다 -> 계속 먹는다

우연히 고기를 구워서 먹는다 -> 맛이 좋았다 -> 이제 계속 구워 먹는다

구운 고기에 우연히 소금을 찍어 먹는다 -> 맛이 더 좋아진다 -> 이제 계속 굽고, 간을 해서 먹는다

이러다가

3일 숙성된 양념육에 대파 기름을 내서 볶아 먹으며, 밥을 곁들인다 <- 같은 느낌으로...

파츠가 늘어나는 것입니다.