823. Binary Trees With Factors (python)

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.

 

  한줄요약   

증가하는 배열 arr의 각 원소를 써서 이진 트리를 만들려고하는데, 

조건1) arr의 원소는 중복사용 가능하고, 

조건2) 자식노드의 곱이 부모 노드가 되야한다. 

이때, 만들수 있는 이진트리 개수를 반환해라.

(이진트리 : 자식노드가 최대 두개인 트리 ) 

 

  IDEA  

흠.. dp로 문제 소분해서 풀 수 있을 것 같다. 

case1) 10이 root로 오는 tree의 개수는 아래와 같이 소분 될 수 있다. 

2, 5, 10 이 들어있다면, 곱셈을 해주는 이유는 좌우가 바뀌여도 카운팅이 되기 때문이다. 

dp[10] = dp[5] * dp[2] +  dp[2] * dp[5]+ dp[10] = 3

dp[5] = 1

dp[2] = 1 

따라서 dp [10] = 3 이다.  

case2) 4이 root로 오는 tree의 개수는 아래와 같이 소분 될 수 있다. 

dp[4] = dp[2] + 1  

 

case3)  2, 3, 5, 6, 15, 30

dp[2] = 1

dp[3] = 1

dp[5] = 1

dp[6] = dp[2] * dp[3]  + dp[3] *dp[2] + dp[6] = 3

dp[15] = dp[3] * dp[5] + dp[5]* dp[3]  + dp[15] = 3 

dp[30] = dp[2] * dp[15] + dp[5]*dp[6]  + dp[6]*dp[5] + dp[15]*dp[2]  +dp[30] 

            =      1   * 3       +  1  *3  +  3*1 + 3*1 + 1  

 

다시 나열하면, 

root = 2, 3, 5, 애네들은 다 root일때 1개이고, 

root =6   =>   [6], [6,2,3] [6,3,2],   => 3개

root = 15 =>  [3,5,15] [5,3,15],[15] =>  3개 

root = 30 =>  13개 
                      [30,2,15], [30, 2, 15, 3, 5], [30, 2, 15, 5, 3]   => 3

                      [30,15,2], [30, 15, 3, 5, 2], [30, 15, 5, 3, 2]   => 3

                      [30, 5, 6], [30, 5, 2, 3] , [30, 5, 3, 2]   => 3

                      [30, 6, 5], [30, 2, 3, 5], [30, 3, 2, 5]    => 3
                      [30]  => 1개

 

 코드 구현 

class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        
        modulo = 1000000007
        dp = [1]*len(arr)
        arr.sort()
        
        cnt=0        
        index = { x : i for i,x in enumerate(arr)} 
      
        for i in range(len(arr)):                            
            for j in range(i):                
                if arr[i]%arr[j] ==0:
                    right = arr[i]/arr[j]
                    if right in index:
                        dp[i]+=dp[j] * dp[index[right]]                       
                        dp[i] %= modulo
        print(dp)
        return sum(dp) % modulo