Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 동적 계획법으로 풀어보는 인수 이진 트리(Binary Trees With Factors) 문제

문제 설명

1보다 큰 양의 정수로 이루어진 리스트가 있다고 가정해 봅시다. 이 정수들을 사용하여 이진 트리를 만들어야 하며, 각 숫자는 원하는 만큼 여러 번 재사용할 수 있습니다. 단, 하나의 조건이 붙습니다. 리프 노드가 아닌 모든 노드는 반드시 자식 노드 값들의 곱(product)이 되어야 한다는 것입니다.

그렇다면 주어진 숫자들로 총 몇 개의 이진 트리를 만들 수 있을까요? 정답은 매우 커질 수 있으므로 10^9 + 7로 나눈 나머지를 반환해야 합니다.

예를 들어 입력이 [2, 4, 5, 10]이라면 다음과 같이 총 7개의 트리를 만들 수 있으며, 따라서 답은 7이 됩니다.

  • [2]
  • [4]
  • [5]
  • [10]
  • [4, 2, 2] : 4 = 2 × 2
  • [10, 2, 5] : 10 = 2 × 5
  • [10, 5, 2] : 10 = 5 × 2

접근 방법: 동적 계획법(DP)

이 문제는 동적 계획법을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

먼저 배열을 오름차순으로 정렬한 뒤 작은 값부터 차례대로 처리하면서, '각 숫자를 루트로 삼는 이진 트리의 개수'를 누적해 나갑니다. 어떤 수 A[i]가 A[j]로 나누어떨어지고(A[i] % A[j] == 0), 그 몫인 A[i]/A[j] 역시 배열 안에 존재한다면, A[j]와 A[i]/A[j]를 각각 좌우 자식으로 갖는 새로운 트리를 만들 수 있습니다. 이때 두 자식을 루트로 하는 트리 개수의 곱만큼 경우의 수가 추가됩니다.

알고리즘 단계

  1. dp 맵 정의 : dp[x]는 x를 루트로 하는 이진 트리의 개수를 의미합니다.
  2. 정렬 및 초기화 : 배열 A를 오름차순으로 정렬하고, n := A의 크기, ret := 0으로 설정합니다.
  3. i를 0부터 n-1까지 반복 :
    • dp[A[i]]를 1 증가시킵니다. (자기 자신 하나만으로 구성된 단일 노드 트리)
    • j를 0부터 i-1까지 반복하면서, A[i] % A[j] == 0이면 dp[A[i]] += dp[A[j]] * dp[A[i] / A[j]]를 더해 줍니다.
  4. 결과 누적 : ret := ret + dp[A[i]]
  5. 반환 : 최종 결과 ret을 반환합니다.

아래 예제 코드를 통해 더 자세히 살펴보겠습니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int MOD = 1e9 + 7;
int add(lli a, lli b){
   return ((a % MOD) + (b % MOD)) % MOD;
}
int mul(lli a, lli b){
   return ((a % MOD) * (b % MOD)) % MOD;
}
class Solution {
   public:
   int numFactoredBinaryTrees(vector<int>& A) {
      unordered_map <int, int> dp;
      sort(A.begin(), A.end());
      int n = A.size();
      int ret = 0;
      for(int i = 0; i < n; i++){
         dp[A[i]] += 1;
         for(int j = 0; j < i; j++){
            if(A[i] % A[j] == 0){
               dp[A[i]] = add(dp[A[i]], mul(dp[A[j]], dp[A[i] / A[j]]));
            }
         }
         ret = add(ret, dp[A[i]]);
      }
      return ret;
   }
};
main(){
   vector<int> v1 = {2,4,5,10};
   Solution ob;
   cout << (ob.numFactoredBinaryTrees(v1));
}

입력

[2,4,5,10]

출력

7

코드 설명

add()와 mul() 함수는 모듈러 연산 과정에서 값이 커져 발생할 수 있는 오버플로를 방지하기 위해, 두 피연산자에 각각 MOD를 먼저 적용한 후 연산을 수행합니다. 메인 로직인 numFactoredBinaryTrees() 함수에서는 unordered_map을 사용하여 각 숫자별 트리 개수를 빠르게 조회하고, 이중 반복문을 통해 모든 (i, j) 쌍을 검사합니다. 전체 시간 복잡도는 O(n²)이며, 공간 복잡도는 O(n)입니다.