Count the Number of Ideal Arrays

HardMathDynamic ProgrammingCombinatoricsNumber Theory

문제 설명

  • 두 개의 정수 n과 maxValue가 주어집니다.
  • 이상적인 배열(ideal array)의 조건:
    • 배열의 길이는 n입니다.
    • 모든 원소 arr[i]는 1부터 maxValue 사이의 값입니다.
    • 각 원소 arr[i]는 이전 원소 arr[i-1]로 나누어 떨어져야 합니다.
  • 길이가 n인 서로 다른 이상적인 배열의 개수를 반환해야 합니다.
    • 결과값이 매우 클 수 있으므로 109+710^9 + 7로 나눈 나머지를 반환해야 합니다.

문제 풀이

Dynamic Programming & Combinatorics

💡 아이디어

  1. 이상적인 배열은 증가하는 배열(non-decreasing) 입니다.
  2. 동적 계획법을 사용하여, 점점 증가하는(strictly increasing) 이상적인 배열의 개수를 계산합니다.
  3. 조합론을 사용하여, 실제 답(길이가 n인 이상적인 배열의 개수)를 도출합니다.

동적 계획법 점화식

  • dp[i][j]: 길이가 i고, j로 끝나는 점점 증가하는 이상적인 배열의 개수.
  • dp[i][j] = sum(dp[i-1][k])
    • 단, j는 k로 나누어 떨어져야 함(즉, k는 j의 약수)

조합론을 통한 답 도출하기

  • 점점 증가하는 이상적인 배열에서 원래 문제인 이상적인 배열로 변환하려면, 각 원소를 반복해서 사용할 수 있습니다.
    • 예: [1, 2, 4]라는 점점 증가하는 배열 → [1, 1, 2, 2, 4]와 같은 길이가 5인 이상적인 배열을 생성
  • Stars and Bars 기법으로 계산할 수 있습니다.
    • n개의 위치에 k개의 서로 다른 수를 배치하는 방법
    • 조합 공식: C(n - 1, k - 1)
  • 실제 답 = C(n - 1, k - 1) * 길이가 k인 점점 증가하는 이상적인 배열의 개수의 합
export function idealArrays(n: number, maxValue: number): number {
  const MOD = 10 ** 9 + 7;
 
  /**
   * 점점 증가하는 이상적인 배열의 최대 길이는 14입니다.
   * 2^14 > 10,000 가능한 가장 긴 점점 증가하는 이상적 배열은 [1, 2, 4, 8, ..., 8192]입니다.
   */
  const MAX_LEN = Math.min(n, 14);
 
  // dp[i][j]는 길이 i의 j로 끝나는 이상적인 배열의 개수
  const dp = Array.from({ length: MAX_LEN + 1 }, () => new Array<number>(maxValue + 1).fill(0));
 
  // `maxValue`까지 모든 수에 대한 약수
  const divisors = getDivisors(maxValue);
 
  // 길이가 1인 이상적인 배열의 개수는 1로 초기화합니다.
  for (let i = 1; i <= maxValue; i++) {
    dp[1][i] = 1;
  }
 
  /**
   * dp[i][j] = sum(dp[i-1][k])
   * 단, j는 k로 나누어 떨어져야 함 (즉, k는 j의 약수)
   */
  for (let i = 2; i <= MAX_LEN; i++) {
    for (let j = 1; j <= maxValue; j++) {
      for (const k of divisors.get(j) ?? []) {
        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
      }
    }
  }
 
  // dp[i][0] = 길이가 i인 점점 증가하는 이상적인 배열의 개수
  for (let i = 1; i <= MAX_LEN; i++) {
    for (let j = 1; j <= maxValue; j++) {
      dp[i][0] = (dp[i][0] + dp[i][j]) % MOD;
    }
  }
 
  /**
   * 조합론을 사용한, 길이가 i인 점점 증가하는 이상적인 배열의 개수로부터
   * 길이가 n인 증가하는 이상적인 배열의 총 개수를 도출
   */
  let answer = 0n;
  for (let i = 1; i <= MAX_LEN; i++) {
    answer += nCk(n - 1, i - 1) * BigInt(dp[i][0]);
    answer %= BigInt(MOD);
  }
  return Number(answer);
}
 
// "n Choose k"를 계산
function nCk(n: number, k: number): bigint {
  let result = 1n;
  for (let i = 1; i <= k; i++) {
    result = (result * BigInt(n - (i - 1))) / BigInt(i);
  }
  return result;
}
 
// `maxValue`까지의 모든 수에 대한 약수들을 계산
function getDivisors(maxValue: number): Map<number, number[]> {
  const divisors = new Map<number, number[]>();
  for (let value = 1; value <= maxValue; value++) {
    divisors.set(value, []);
  }
  for (let value = 1; value <= maxValue; value++) {
    let multiply = 2;
    while (value * multiply <= maxValue) {
      divisors.get(value * multiply)?.push(value);
      multiply += 1;
    }
  }
  return divisors;
}

복잡도

  • 시간 복잡도: O(maxValue⋅log⁡2maxValue)O(maxValue \cdot \log_{2} maxValue)
  • 공간 복잡도: O(maxValue⋅log⁡2maxValue)O(maxValue \cdot \log_{2} maxValue)
LeetCode
Count the Number of Ideal Arrays
https://leetcode.com/problems/count-the-number-of-ideal-arrays