.leetcode(96. Unique Binary Search Trees)

문제

https://leetcode.com/problems/unique-binary-search-trees/

문제 풀기 전

1. 처음에는 subarray로 푸르는데 recursive가 헷갈려서 중단
2. 이게보니 정렬된 요소의 갯수에 따라 답이 정해져 있음 1->1 2->2 3->5

직접 푼 풀이

소요시간: 36분(08:48 ~ 09:24)

class Solution {
    public int numTrees(int n) {
        int[] elements = new int[n];
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int j=2; j<=n; j++) {
            for(int i=0; i<j; i++) {
                dp[j] += dp[j-i-1] * dp[i];
            }
        }
        return dp[n];
    }
}

느낀점

1. 정렬된 요소라는 가정하에 갯수에 따라 몇개의 정렬된 트리가 나올 수 있는지가 정해져 있기 때문에 어느 요소를 중점으로 트리를 쪼갤지만 생각하면 된다. 그런데 큰 요소를 구하기 위해 그전의 작은 요소들을 구해야하므로 2부터 목표n까지 차근차근 구해가는 방식이다.
2. 카탈란 수(Catalan number)를 통해서 풀기도 하던데 새로운 개념이라 좀 더 조사해봐야겠다.

• https://ko.wikipedia.org/wiki/%EC%B9%B4%ED%83%88%EB%9E%91_%EC%88%98

솔루션 공부 후 추가로 푼 풀이

#카탈란 수로 풀기

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)