[Leetcode][823] Binary Trees With Factors

문제 : leetcode.com/problems/binary-trees-with-factors/

---

2이상의 정수 배열 arr이 주어진다.

arr 배열의 수들을 노드로 가지는 이진트리를 만들고자 한다.

정수들은 중복으로 사용할 수 있고 각 노드들의 값은 자식노드들의 곱과 같다.

조건을 만족하며 만들 수 있는 이진트리의 개수를 구하라.

---

num으로 만들수 있는 서브트리의 수를 메모이제이션으로 캐싱한다.

dp[num] = num을 루트로 하는 이진트리의 갯수.

dp[num] = dp[num1] x dp[num2] // num1 x num2 = num

점화식은 위와 같다.

따라서, 곱해서 num이 나오는 num1, num2의 세트 배열을 구해야 된다.

2중 for문을 돌려서 arr배열의 요소들을 곱해서 num이 나오는 num1, num2 배열을 구한 뒤, 재귀함수를 돌려서 위 점화식을 사용하여 정답을 구할 수 있다.

정답은 dp[arr 배열]의 합이다.

 

시간복잡도는 O(N^2).

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/823.%20Binary%20Trees%20With%20Factors.cpp