2338. Count the Number of Ideal Arrays


Leetcode Hard 100

https://leetcode.com/problems/count-the-number-of-ideal-arrays/description

📖 문제 해석

길이가 n인 0‑인덱스 배열 arr가 “이상적(ideal)”이려면 두 가지 조건을 만족해야 합니다.

  1. 모든 원소는 1 이상 maxValue 이하
  2. i > 0일 때마다 arr[i]가 arr[i-1]로 나누어진다. 즉, 다음 원소는 이전 원소의 배수여야 합니다.

우리가 구해야 하는 것은 가능한 서로 다른 이상적 배열의 개수이며, 결과는 1_000_000_007으로 나눈 나머지입니다.

간단한 예로 n = 3, maxValue = 4를 생각해 보면,

  • 시작을 1로 잡으면 (1,1,1), (1,1,2), (1,1,3), (1,1,4), (1,2,2), (1,2,4), (1,3,3), (1,4,4) 등 다양하게 나옵니다.
  • 핵심 제약은 “이전 값이 다음 값을 나눈다”는 것입니다. 그래서 값은 비내림(non‑decreasing)이고, ‘증가’가 일어나는 지점에서 항상 배수 관계로만 점프할 수 있습니다.

제약을 보면 n과 maxValue 모두 최대 10<sup>4</sup>로, 단순 완전탐색은 불가능합니다.

🧠 첫 시도와 그 한계

가장 먼저 떠오르는 방법은 “앞에서부터 채우기”입니다. arr[0]를 1..maxValue 중 하나로 고른 뒤, arr[1]은 그 배수들 중에서 고르고… 이런 식으로 모든 길이 n을 만드는 DFS/DP를 생각하게 됩니다. 하지만 이 접근을 정직하게 펼치면 상태의 가지수가 너무 큽니다. 예를 들어 arr[i-1] = 1인 순간 다음 값은 1..maxValue 전부 열립니다. 분기 팽창은 금세 폭발합니다.

또 다른 생각은 “모든 값에 대해 배수 목록을 미리 만들어 두고 그래프 위 경로 개수를 세자”입니다. 각 정수 x에서 간선은 x → kx (kx ≤ maxValue)입니다. 길이 n의 경로 수를 세는 전형적인 DP처럼 보이지만, n = 10^4 길이의 경로를 그대로 세는 건 여전히 비쌉니다. 한 단계마다 평균적으로 여러 배수로 퍼지기 때문에, 전체 연산량이 O(n * maxValue * (평균 배수 수))로 올라가고, 이 평균 배수 수는 1/1 + 1/2 + … + 1/maxValue ≈ log maxValue 수준의 조화급수로 합쳐져도, n이 크기 때문에 부담스럽습니다.

무엇보다, 여기에는 중복이 많습니다. 예를 들어 (1, 2, 2, 4)와 (1, 1, 2, 4)는 “값이 실제로 바뀌는 지점”만 보면 둘 다 1 → 2 → 4라는 같은 압축(Compressed) 사슬을 공유합니다. 이 중복을 잡아내지 못하면 비효율을 피하기 어렵습니다.

💡 결정적 통찰

문제의 본질은 “배수 사슬”입니다. a | b(a가 b를 나눈다) 관계만 허용되므로, 배열에서 값이 실제로 바뀌는 순간들만 뽑아 보면 다음과 같은 압축 사슬이 됩니다.

v1 → v2 → v3 → … → vℓ   (각 vi+1은 vi의 배수, 모든 vi ≤ maxValue)

여기서 중요한 관찰이 두 가지 있습니다.

첫째, 길이 ℓ의 압축 사슬 개수만 알면, 길이 n짜리 원본 배열의 개수로 확장할 수 있습니다.
길이 ℓ의 사슬을 n칸에 배치하려면, n-1개의 경계 사이에서 “값이 바뀌는 지점”을 정확히 ℓ-1번 고르면 됩니다. 이는 표준 조합론 결과로 C(n-1, ℓ-1)입니다. 예를 들어 ℓ=3이면, n-1칸 중 2곳에서 값이 바뀌게 표시하면 (v1, …, v1, v2, …, v2, v3, …, v3) 꼴이 됩니다.

📘 압축 사슬 → 전체 배열 (Change-point 조합)
길이 ℓ개의 구간(값 블록)을 길이 n의 일렬 칸에 늘어놓는 방법 수는 구간 경계 ℓ-1개를 n-1개의 칸 사이에 배치하는 경우의 수와 동일하여 C(n-1, ℓ-1)이 됩니다.

둘째, 가능한 압축 사슬의 최대 길이는 매우 작다는 점입니다. 매 단계에서 최소한 2배가 되어야 순수한 배수 증가를 계속할 수 있으므로, 어떤 값이든 maxValue 안에서 만들 수 있는 배수 사슬의 길이는 대략 log2(maxValue)를 넘기 어렵습니다. maxValue ≤ 10<sup>4</sup>면 대략 14를 조금 넘는 수준이라, ℓ을 20 정도로 자르면 충분합니다. 이 덕분에 “사슬 길이” 차원에서의 DP가 실용화됩니다.

이제 전략은 명확합니다.

  1. 길이 ℓ별로 가능한 압축 사슬 수 tot[ℓ]를 미리 계산합니다.
  2. 최종 답은 ∑_{ℓ=1..min(n, LOG)} tot[ℓ] * C(n-1, ℓ-1)입니다.

압축 사슬 수는 다음 점화로 구할 수 있습니다. cnt[ℓ][x] = “길이 ℓ의 사슬이 x에서 시작하는 경우의 수”.

  • 초기값: cnt[1][x] = 1 (길이 1은 자기 자신뿐)
  • 전이: cnt[ℓ][x] = ∑_{k ∈ {2x, 3x, …} ≤ maxValue} cnt[ℓ-1][k]
    (다음 값은 x의 배수여야 하므로 x → kx로 이동)

각 ℓ에 대해 tot[ℓ] = ∑_{x=1..maxValue} cnt[ℓ][x]로 합치면 됩니다.

이 접근이 잘 맞아떨어지는 이유는,

  • ‘배수 그래프’가 정방향(작은 수 → 큰 수) DAG라 역전이가 없고,
  • 가능한 길이 ℓ의 상한이 작아 2차원 DP에 가깝게 줄어들며,
  • 마지막에 C(n-1, ℓ-1)로 중복을 정확히 한 번만 세어주기 때문입니다.

🔍 알고리즘 동작 예시

n = 6, maxValue = 10을 가정해 보겠습니다. 편의상 LOG = 20이지만 실제로는 5~6 정도까지만 값이 나옵니다.

  1. ℓ = 1
    모든 시작값 x에 대해 cnt[1][x] = 1. 따라서 tot[1] = 10.
  2. ℓ = 2
    cnt[2][x] =x의 배수 개수만큼입니다. 예를 들어
    • x = 1 → 배수 {2,3,4,5,6,7,8,9,10} → 9
    • x = 2 → 배수 {4,6,8,10} → 4
    • x = 3 → {6,9} → 2
    • x = 4 → {8} → 1
    • x = 5 → {10} → 1
      나머지는 0. 이를 모두 더한 것이 tot[2].
  3. ℓ = 3
    cnt[3][x] = ∑ cnt[2][k] for k가 x의 배수.
    예를 들어 x=1이면 k ∈ {2..10}, 이들의 cnt[2][k]를 모두 더합니다.
    이렇게 누적하면 tot[3]이 나옵니다.

이렇게 얻은 tot[ℓ]를 이용해 최종 합을 계산합니다.

  • 예를 들어 ℓ=3 사슬 하나를 길이 6 배열로 확장하는 가짓수는 C(5,2) = 10입니다.
  • 결국 answer = tot[1]*C(5,0) + tot[2]*C(5,1) + tot[3]*C(5,2) + …가 됩니다.

💻 전체 소스 코드

#include <bits/stdc++.h><br>using namespace std;<br><br>class Solution {<br>public:<br>    static constexpr int MOD = 1'000'000'007;<br><br>    int idealArrays(int n, int maxValue) {<br>        // LOG는 가능한 압축 사슬 길이의 상한.<br>        // maxValue <= 1e4이므로 log2(maxValue) ~ 14.x → 20이면 충분.<br>        int LOG = min(20, n);<br><br>        // cnt[ℓ][x] = 길이 ℓ의 압축 사슬이 값 x에서 시작하는 가짓수<br>        // 인덱싱 편의상 1..maxValue 사용, 0은 비움<br>        vector<vector<int>> cnt(LOG + 1, vector<int>(maxValue + 1, 0));<br><br>        // tot[ℓ] = 길이 ℓ의 압축 사슬 전체 가짓수 (시작값 x를 모두 합산)<br>        vector<int> tot(LOG + 1, 0);<br><br>        // ℓ = 1 초기화: 모든 x에서 길이 1 사슬은 자기 자신 하나뿐<br>        for (int x = 1; x <= maxValue; ++x) cnt[1][x] = 1;<br>        tot[1] = maxValue % MOD;<br><br>        // ℓ >= 2 전이<br>        // cnt[ℓ][x] = sum_{k in {2x,3x,...<=maxValue}} cnt[ℓ-1][k]<br>        // x를 큰 값부터 내려오며 업데이트해도 상호 의존성 문제는 없음(ℓ-1 층만 읽음).<br>        for (int len = 2; len <= LOG; ++len) {<br>            long long sumLen = 0; // tot[len] 누적용(overflow 대비 64-bit)<br>            for (int x = maxValue; x >= 1; --x) {<br>                long long ways = 0;<br>                for (int k = x * 2; k <= maxValue; k += x) {<br>                    ways += cnt[len - 1][k];<br>                    if (ways >= (1LL<<62)) ways %= MOD; // 드물지만 안전빵<br>                }<br>                cnt[len][x] = static_cast<int>(ways % MOD);<br>                sumLen += cnt[len][x];<br>                if (sumLen >= (1LL<<62)) sumLen %= MOD;<br>            }<br>            tot[len] = static_cast<int>(sumLen % MOD);<br>        }<br><br>        // 조합 C(i, j) = comb[i][j], i up to n-1, j up to LOG-1<br>        // 필요한 건 C(n-1, ℓ-1)이므로 테이블은 크기 (n x (LOG)).<br>        vector<vector<int>> comb(n, vector<int>(LOG, 0));<br>        comb[0][0] = 1;<br>        for (int i = 1; i < n; ++i) {          // i == (선택 가능한 경계 수)<br>            int up = min(i, LOG - 1);<br>            for (int j = 0; j <= up; ++j) {    // j == (실제 선택한 경계 수)<br>                if (j == 0 || i == j) comb[i][j] = 1;<br>                else {<br>                    comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % MOD;<br>                }<br>            }<br>        }<br><br>        // 최종 합산: answer = sum_{ℓ=1..LOG} tot[ℓ] * C(n-1, ℓ-1)<br>        long long ans = 0;<br>        for (int len = 1; len <= LOG; ++len) {<br>            // (n-1)개 경계에서 (len-1)개를 고르는 조합수<br>            int waysPlace = comb[n-1][len-1];<br>            ans = (ans + 1LL * tot[len] * waysPlace) % MOD;<br>        }<br>        return static_cast<int>(ans);<br>    }<br>};<br>

🔁 다른 관점의 해법 (참고)

이 문제는 “각 값의 소인수 분해”를 이용해 dp 없이 바로 계산하는 방식도 유명합니다. 임의의 값 v의 소인수 분해 v = p1^e1 * p2^e2 * ...를 보면, v까지 갈 수 있는 배수 사슬은 각 지수 ei가 단계별로 비내림이 되도록 분배하는 문제로 바뀌고, 이는 ei마다 C(n-1+ei, ei)의 곱으로 나타납니다. 그런 뒤 v = 1..maxValue를 모두 합치면 답이 됩니다. 구현은 소수 체와 조합 전처리가 필요하고, 상수는 작지만 지수 분해 비용을 세심히 관리해야 합니다. 본 글의 DP+조합 방식은 구현이 깔끔하고, log2(maxValue) 상한 덕에 충분히 빠릅니다.

📌 정리와 핵심 포인트

이 문제의 함정은 길이 n이 크다는 이유로 “한 칸씩 채우는 경로 세기”로 가면 중복과 분기 폭발에 갇힌다는 점입니다. 해법은 값이 바뀌는 순간만 남기는 압축 사슬을 먼저 세고, 이 사슬을 길이 n으로 조합론적으로 확장하는 것입니다. 배수 사슬의 길이는 log2(maxValue) 정도로 매우 짧으니, ℓ 차원을 추가한 DP가 오히려 빠르고 간단합니다. 그 결과 answer = ∑ tot[ℓ] * C(n-1, ℓ-1)라는 단정한 형태가 나오고, 구현도 안정적으로 마무리됩니다.

<< Process String with Special Operations II

Similar Posts