배열 arr과 값 k가 주어졌을 때, 배열 전체의 GCD(최대공약수)를 k의 배수가 되도록 만들기 위해 필요한 최소 연산 횟수를 구하는 문제입니다. 여기서 연산이란 특정 요소의 값을 1만큼 증가시키거나 감소시키는 것을 의미합니다.
예를 들어 배열이 {4, 5, 6}이고 k = 5라고 가정해 봅시다. 4를 1 증가시키고, 6을 1 감소시키면 배열은 {5, 5, 5}가 되어 GCD가 5(k의 배수)가 됩니다. 이때 필요한 연산 횟수는 총 2회입니다.
알고리즘 접근 방법
각 요소를 k의 배수에 가장 가깝게 만들면 되므로, 다음 단계를 따라 문제를 해결할 수 있습니다.
- 배열의 모든 요소
e에 대해 아래 조건을 검사합니다. e가 1이 아니고e > k인 경우,e mod k(k로 나눈 나머지)와k - (e mod k)중 더 작은 값을 결과에 더합니다. 즉, 위로 올릴지 아래로 내릴지 더 적은 연산으로 k의 배수에 도달하는 방법을 선택합니다.- 그 외의 경우(
e ≤ k또는e == 1), 해당 값을 k까지 증가시켜야 하므로 결과에k - e를 더합니다. - 모든 요소에 대한 연산 횟수의 합을 반환합니다.
C++ 구현 예제
#include <iostream>
using namespace std;
int countMinOp(int arr[], int n, int k) {
int result = 0;
for (int i = 0; i < n; ++i) {
if (arr[i] != 1 && arr[i] > k) {
// k보다 큰 경우: 나머지 기준으로 올림/내림 중 최소 연산 선택
result += min(arr[i] % k, k - arr[i] % k);
} else {
// k 이하인 경우: k까지 증가시키는 연산 필요
result += k - arr[i];
}
}
return result;
}
int main() {
int arr[] = { 4, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 5;
cout << "Minimum operation required: " << countMinOp(arr, n, k);
}실행 결과
Minimum operation required: 2
동작 원리 설명
위 예제에서 각 요소를 살펴보면 다음과 같습니다.
- 4: k(5) 이하이므로 5까지 증가 → 1회 연산
- 5: 이미 k의 배수이므로 연산 불필요 → 0회
- 6: k보다 크며, 6 mod 5 = 1이므로 min(1, 4) = 1 → 1회 연산
따라서 총 연산 횟수는 2가 됩니다. 이 알고리즘은 배열을 한 번만 순회하면 되므로 시간 복잡도는 O(n)이며, 매우 효율적입니다.