문제 설명
크기가 n인 배열이 주어졌을 때, 배열의 모든 요소를 4로 나누어 떨어지도록 만들기 위해 필요한 최소 연산 횟수를 구하는 것이 목표입니다. 여기서 한 번의 연산(step)은 배열에서 임의의 두 요소를 제거하고, 그 두 요소의 합을 새로운 요소로 배열에 추가하는 것으로 정의됩니다.
예시
입력 배열이 {1, 2, 0, 2, 4, 3}이라면 다음과 같이 2번의 연산만으로 모든 요소를 4의 배수로 만들 수 있습니다.
연산 1: 1 + 3 = 4
연산 2: 2 + 2 = 4
배열에 있는 0과 4는 이미 4로 나누어 떨어지므로 별도의 연산 없이 그대로 두면 됩니다.
알고리즘
- 배열의 모든 요소의 합이 4로 나누어 떨어져야 합니다. 그렇지 않다면 이 작업 자체가 불가능하므로 -1을 반환합니다.
- 크기가 4인 배열(modulus)을 선언하고 0으로 초기화합니다.
- 연산 횟수를 기록할 카운터(count)를 0으로 초기화합니다.
- 입력 배열을 순회하면서 각 요소를 4로 나눈 나머지(mod)를 구합니다.
- modulus 배열에서 해당 나머지 인덱스의 값을 1씩 증가시켜 나머지별 개수를 셉니다.
- modulus[0]은 이미 4로 나누어 떨어지는 요소들의 개수이므로, 다른 요소와 짝을 지을 필요가 없습니다.
- 나머지가 1인 요소와 나머지가 3인 요소는 서로 결합하면 4의 배수가 되므로, 두 개수 중 작은 값만큼 count를 증가시킵니다.
- 나머지가 2인 요소(modulus[2])는 두 개씩 결합하면 4의 배수가 됩니다.
- 짝을 지지 못하고 남은 나머지 1, 3 요소들은 같은 나머지끼리 두 개씩 결합하면 나머지 2 형태가 되므로, modulus[2]에 그 절반을 더합니다.
- 마지막으로 count에 modulus[2]의 절반을 더합니다. 두 요소가 하나의 연산으로 결합되기 때문에 절반을 사용합니다.
- 최종 count 값이 배열의 모든 요소를 4로 나누어 떨어지게 만드는 데 필요한 최소 연산 횟수입니다.
C++ 구현
위 알고리즘을 C++로 구현한 코드는 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
int getMinRequiredSteps(int arr[], int n) {
int count = 0;
int modulus[4] = {0};
int sum = 0;
for (int i = 0; i < n; i++) {
int mod = arr[i] % 4;
sum += mod;
modulus[mod]++;
}
if (sum % 4 != 0) {
return -1;
} else {
if (modulus[1] > modulus[3]) {
count += modulus[3];
}
else {
count += modulus[1];
}
modulus[1] -= count;
modulus[3] -= count;
modulus[2] += modulus[1] / 2;
modulus[2] += modulus[3] / 2;
count += modulus[1] / 2;
count += modulus[3] / 2;
count += modulus[2] / 2;
return count;
}
}
int main() {
int arr[] = {1, 2, 0, 2, 4, 3};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "필요한 최소 연산 횟수 = " << getMinRequiredSteps(arr, n) << endl;
return 0;
}
출력 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.
필요한 최소 연산 횟수 = 2
복잡도 분석
시간 복잡도: O(n) — 배열을 한 번만 순회하면 됩니다.
공간 복잡도: O(1) — 크기가 4로 고정된 보조 배열만 사용하므로 추가 메모리는 일정합니다.