C++로 인접 요소의 GCD가 주어진 배열과 일치하는 새 배열 구성하기

n개의 원소를 가진 배열 A[]가 주어졌을 때, 크기가 n+1인 또 다른 배열 B[]를 구성해야 합니다. 이때 배열 B는 인접한 두 원소의 최대공약수(GCD)가 원래 배열의 값과 일치해야 하며, 즉 GCD(B[i], B[i+1]) = A[i] 조건을 만족해야 합니다. 만약 가능한 답이 여러 개라면, 그중 배열 원소의 합이 가장 작은 하나를 출력하면 됩니다.

예를 들어 A = [1, 2, 3]이라면, 결과 배열은 [1, 2, 6, 3]이 됩니다. 실제로 GCD(1, 2) = 1, GCD(2, 6) = 2, GCD(6, 3) = 3으로 모든 조건을 충족합니다.

접근 방법

배열 A에 원소가 하나만 있다면(예: K), B = [K, K]가 됩니다. 즉 B[0]은 항상 A[0]입니다.

이제 인덱스 i까지 처리가 완료되어 B[i+1]까지 계산된 상태라고 가정해 봅시다. 다음 조건들이 성립해야 합니다.

• GCD(B[i+1], B[i+2]) = A[i+1]
• GCD(B[i+2], B[i+3]) = A[i+2]

B[i+2]는 A[i+1]의 배수이면서 동시에 A[i+2]의 배수여야 하므로, B[i+2] ≥ LCM(A[i+1], A[i+2])가 됩니다. 우리의 목표는 배열의 합을 최소화하는 것이므로, B[i+2]는 가능한 한 가장 작은 값, 즉 LCM(A[i+1], A[i+2])로 선택하는 것이 최적입니다.

정리하면 배열 B는 다음과 같이 구성됩니다.

• B[0] = A[0]
• B[i+1] = LCM(A[i], A[i+1]) (i = 0 ~ n-2)
• B[n] = A[n-1]

예제 코드

#include <iostream>
#include <algorithm>
using namespace std;

int getLCM(int a, int b) {
    return (a * b) / __gcd(a, b);
}

void gcdArray(int A[], int n) {
    cout << A[0] << " ";
    for (int i = 0; i < n - 1; i++)
        cout << getLCM(A[i], A[i + 1]) << " ";
    cout << A[n - 1];
}

int main() {
    int A[] = { 1, 2, 3 };
    int n = sizeof(A) / sizeof(A[0]);
    cout << "Constructed array: ";
    gcdArray(A, n);
}

실행 결과

Constructed array: 1 2 6 3

코드 설명

getLCM 함수는 두 수의 곱을 두 수의 GCD로 나누어 최소공배수(LCM)를 계산합니다. gcdArray 함수는 먼저 첫 번째 원소 A[0]을 출력하고, 이후 각 인접 원소 쌍의 LCM을 순서대로 출력한 뒤 마지막에 A[n-1]을 출력하여 완전한 배열 B를 만듭니다. 이 방식은 각 위치에서 최솟값을 선택하므로 자연스럽게 전체 합이 최소인 해를 보장합니다.