C++ DP로 풀기: 인접한 요소끼리 서로를 나누어 떨어지게 하는 배열의 개수 구하기

문제 개요

두 개의 정수 'one'(배열의 길이)과 'another'(요소의 최댓값)가 주어집니다. 목표는 다음 조건을 모두 만족하는 배열의 개수를 구하는 것입니다.

배열의 모든 요소는 1 이상 'another' 이하의 범위 안에 있어야 합니다.
인접한 두 요소마다 한쪽이 다른 쪽을 나누어 떨어지게 해야 합니다. 즉, 임의의 i에 대해 arr[i]가 arr[i+1]의 약수 또는 배수여야 합니다.
배열의 길이는 정확히 'one'이어야 합니다.

예제 1

입력

one = 3, another = 2

출력

인접한 요소끼리 서로를 나누는 배열의 개수: 8

설명

가능한 배열은 다음과 같습니다:
[1,1,1], [1,1,2], [1,2,1], [1,2,2], [2,1,1], [2,1,2], [2,2,1], [2,2,2]

예제 2

입력

one = 2, another = 3

출력

인접한 요소끼리 서로를 나누는 배열의 개수: 7

설명

가능한 배열은 다음과 같습니다:
[1,1], [2,2], [3,3], [1,2], [2,1], [1,3], [3,1]

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

각 배열의 첫 번째 요소는 [1, another] 범위 내의 어떤 수든 될 수 있습니다. 그다음 요소는 나눗셈 조건을 유지하기 위해 항상 이전 요소의 배수 또는 약수여야 하며, 그 값 역시 'another'를 초과할 수 없습니다. 이러한 성질을 이용하면 동적 계획법으로 중복 계산 없이 문제를 효율적으로 해결할 수 있습니다.

2차원 배열 arr[][]를 사용합니다. 길이가 1인 배열은 각 숫자 자신 하나뿐이므로 arr[1][j] = 1로 초기화하고, 이후 아래 점화식으로 테이블을 채워 나갑니다.

arr[i][j] = Σ arr[i-1][k]
(단, k는 j의 약수 또는 j의 배수이면서 'another' 이하인 수)

알고리즘 단계

정수 one과 another를 입력받습니다.
함수 adjacent_elements(first, second)는 조건을 만족하는 배열의 개수를 반환합니다.
count를 0으로 초기화하고 2차원 배열 arr[size][size]를 선언한 뒤, memset으로 모두 0으로 채웁니다.
약수를 저장할 벡터 vec과 배수를 저장할 벡터 vec_2를 준비합니다.
두 개의 for 루프(i는 1부터 second까지, j는 2*i부터 second까지 i씩 증가)를 돌며 vec[j]에 i를, vec_2[i]에 j를 추가합니다. j 루프가 끝난 후에는 vec[i]에 i 자신도 추가해 자기 자신도 나눌 수 있음을 처리합니다.
for 루프로 arr[1][i] = 1을 설정합니다.
DP 테이블을 다시 순회하면서 vec[j]와 vec_2[j]를 참조해, 이전 행(arr[i-1])의 약수·배수 위치에 저장된 경우의 수를 arr[i][j]에 더합니다.
마지막으로 모든 arr[first][i] 값을 count에 누적하고, vec[i]와 vec_2[i]를 비웁니다.
count를 결과로 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
#define size 1000
int adjacent_elements(int first, int second){
    int count = 0;
    int arr[size][size];
    memset(arr, 0, sizeof arr);
    vector<int> vec[size], vec_2[size];
    memset(vec, 0, sizeof vec);
    memset(vec_2, 0, sizeof vec_2);
    for (int i = 1; i <= second; i++){
        for (int j = 2*i; j <= second; j += i){
            vec[j].push_back(i);
            vec_2[i].push_back(j);
        }
        vec[i].push_back(i);
    }
    for (int i = 1; i <= second; i++){
        arr[1][i] = 1;
    }
    for (int i = 2; i <= first; i++){
        for (int j = 1; j <= second; j++){
            arr[i][j] = 0;
            for (auto it: vec[j]){
                arr[i][j] += arr[i-1][it];
            }
            for (auto it : vec_2[j]){
                arr[i][j] += arr[i-1][it];
            }
        }
    }
    for (int i = 1; i <= second; i++){
        count = count + arr[first][i];
        vec[i].clear();
        vec_2[i].clear();
    }
    return count;
}
int main(){
    int one = 2, another = 2;
    cout<<"Count of arrays in which all adjacent elements are such that one of them divide the another are: "<<adjacent_elements(one, another);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Count of arrays in which all adjacent elements are such that one of them divide the another are: 4

복잡도 및 마무리

전처리 단계에서 각 수의 약수·배수 관계를 구하는 데는 약 O(N log N)(N = another)의 시간이 걸리고, DP 테이블을 채우는 단계는 O(one × another × 평균 인접 요소 수)의 시간 복잡도를 가집니다. 공간 복잡도는 O(N²)입니다. 이처럼 동적 계획법을 활용하면 가능한 모든 배열을 일일이 생성하는 완전 탐색 방식보다 훨씬 빠르게 정답을 구할 수 있습니다.