Catalan Numbers

외젠 샤를 카탈랑이 1838년에 제안한 수열로
카탈랑 수는 조합에서 자주 나오는 수열이며 아래의 점화식으로 나타낼 수 있다

 

 

n 번째 카탈랑 수는 아래의 점화식으로 나타낼 수 있다.

 

예를 들어 9번째 카탈랑수를 구한다면 아래의 표 처럼 구할 수 있다.

 

 

-출처 나무위키-

 

import java.util.ArrayList;

public class CatalanNumbers {

    public static int solution(int n) {
        int result;

        ArrayList<Integer> list = new ArrayList<>();

        list.add(1);

        for (int i = 0; i <= n-1; i++) {
            int c = 0;
            for (int j = 0; j <= i; j++) {
                c = c + list.get(j) * list.get(i-j);
            }
            list.add(c);
        }

        result = list.get(n);
        return result;
    }


    public static void main(String[] args) {
        
        System.out.println(solution(0));
        System.out.println(solution(2));
        System.out.println(solution(5));
        System.out.println(solution(7));
    }
}

 

n 번째의 카탈랑수를 구하기 위해서는 1 ~ n-1 번째의 카탈랑수를 전부 구해야한다.

이것을 재귀적으로도 풀수 있는 방법이 있지만, 아직 재귀적방법이 많이 헷갈려서 for 문을 이용하여 구현하였다.

 

인덱스 관리가 쉬운 ArrayList 를 사용하여 카탈랑수를 add 하여 관리하였다.

 

for 문 안에 있는 카탈링 수를 구하는 코드인 c = c + list.get(j) * list.get(i-j) 에서 list 의 인덱스에서 어떤 값을 가져와야할지 고민하는 부분에서 시간이 오래 걸렸다. 직접 손으로 n 번째 카탈링 수를 구할때 필요한 c 의 인덱스를 나열하면서 규칙을 찾아 해결 할 수 있었다.