[LeetCode] 823 | Binary Trees With Factors | Python

---

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

---

문제

Given an array of unique integers, arr, where each integer arr[i] is strictly greater than 1.

We make a binary tree using these integers, and each number may be used for any number of times. Each non-leaf node's value should be equal to the product of the values of its children.

Return the number of binary trees we can make. The answer may be too large so return the answer modulo $10^9 + 7$.

 

 

---

조건

• 1 <= arr.length <= 1000
• 2 <= arr[i] <= $10^9$
• All the values of arr are unique.

---

내 풀이

다이나믹 프로그래밍으로 문제를 푼다.

arr안에서 임의의 원소 a, b, c를 뽑았을 때, a*b=c를 만족시킨다면, dp[c] += dp[a]*dp[b]가 된다.

---

코드

class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        N = len(arr)
        arr.sort()
        modulo = 10**9 + 7
        dp = [1]*N
        
        idxs = {}                       # arr안의 숫자에 대한 index를 저장
        for idx, num in enumerate(arr):
            idxs[num] = idx
        
        for i in range(1, N):
            for j in range(i):
                if arr[i]%arr[j] == 0:  # arr[i]가 arr[j]의 배수라면
                    if arr[i]//arr[j] in idxs:  # arr[j] * x = arr[i]를 만족시키는 x가 arr에 존재한다면
                        dp[i] += dp[idxs[arr[i]//arr[j]]] * dp[j]   # 그 x의 index를 idx라 할 때, dp[i] += dp[idx]*dp[j]
                        dp[i] %= modulo
                        
        return sum(dp)%modulo