[LeetCode] 823. Binary Trees With Factors

https://leetcode.com/problems/binary-trees-with-factors/

Binary Trees With Factors - LeetCode

leetcode - 823. Binary Trees With Factors

문제 유형 : 다이나믹 프로그래밍 / 수학

문제 난이도 : Medium

 

 

문제

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보다 크다. 우리는 이 정수들로 이진 트리를 만든다. 그리고 각 숫자는 얼마든지 쓰일 수 있다.

리프 노드가 아닌 노드들은 자식들의 곱의 형태로 이루어져야 한다.

 

만들 수 있는 이진트리의 수를 구하시오. 정답이 너무 커질 수도 있기 때문에, 1e9+7로 나누시오.

 

풀이

오름차순으로 배열을 정렬해준다. 작은 숫자들의 트리를 다 만들어야지 큰 수의 서브트리의 경우의 수를 dp로 빠르게 구할 수 있기 때문이다.

dp테이블을 만든다. dp[root]는 root를 루트로 하는 트리의 개수이다. 기본적으로 값은 자기 자신인 1이 가능하기 때문에, dp테이블 초기화를 1로 한다.

첫 번째부터 시작한다. 

배열의 요소 중에서 자신을 제외한 약수 쌍에서 각각을 루트로 하는 서브트리의 개수를 곱한 값을 저장한다.

2,4가 있다고 하면, dp[2]는 1개이고, dp[4]는 dp[2]*dp[2]로 1+1 = 2가 된다.

이 것을 모두 누적해주면 된다.

 

코드

C++

class Solution {
public:
    const int MOD = 1e9 + 7;

    int numFactoredBinaryTrees(vector<int>& arr) {
        sort(arr.begin(), arr.end());

        int n = arr.size();
        vector<long long> dp(n, 1);

        unordered_map<int, int> index;

        for (int i = 0; i < n; i++) {
            index[arr[i]] = i;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] % arr[j] == 0) {
                    int quotient = arr[i] / arr[j];
                    if (index.find(quotient) != index.end()) {
                        dp[i] = (dp[i] + dp[j] * dp[index[quotient]]) % MOD;
                    }
                }
            }
        }

        long long total = 0;
        for (int i = 0; i < n; i++) {
            total = (total + dp[i]) % MOD;
        }

        return static_cast<int>(total);
    }
};