96. Unique Binary Search Trees

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

Unique Binary Search Trees - LeetCode

 

임의의 정수가 주어졌을 때, 이진 트리로 구성될 수 있는 모든 가짓수를 구하는 문제.

직전 풀었던 문제와 비슷한 개념으로 접근하면 될거 같다.

https://makga.tistory.com/122

1부터 n까지 모든 정수가 root 노드에 존재할 수 있고, left tree는 root보다 적은 수만, right tree는 root보다 큰 수만 온다는 조건으로 계산을 한다.

다만 timelimit이 있으므로 이미 계산된 숫자의 경우의 수를 map에 저장해두고 참조하며 반복 계산은 하지 않도록 한다.

 

class Solution {
public:
    int solve(int val)
    {
        if (val == 0 || val == 1)
        {
            map_[val] = 1;
            return map_[val];
        }
        
        /*
        이 문제의 경우는 값이 0인 경우가 없어 문제는 안되지만
        다른 문제의 경우 []로 접근시 empty와 0의 구분 문제가 생김
        */
        auto iter = map_.find(val);
        if (iter != map_.end()) {
            return iter->second;
        }
        
        /*
        val 미만의 값들(left tree)의 경우의 수를 구하고
        val 초과의 갑들(right tree)의 경우의 수를 구하고
        곱셈으로 모든 경우의 수를 구한다
        */
        
        int ret = 0;
        
        for (int k = 1; k <= val; ++k)
        {
            // 7 ~ 15든 1 ~ 9든 경우의 수는 똑같나..
            ret += solve(k - 1) * solve(val - k);
        }
        
        map_[val] = ret;        
        return ret;
    }
    int numTrees(int n) {
        return solve(n);
    }
private:
    unordered_map<int, int> map_;
};

leetcode