C++에서 배열 합을 짝수로 만들기 위한 최소 제거 횟수 구하기

문제 설명

N개의 정수로 구성된 배열 arr[]가 주어졌을 때, 남은 요소들의 합이 짝수가 되도록 만들기 위해 배열에서 제거해야 하는 요소의 최소 개수를 구하는 프로그램을 작성해야 합니다.

예시

입력 배열이 {10, 20, 30, 5}라고 가정해 보겠습니다. 이 배열의 전체 합은 65로 홀수입니다. 따라서 합을 짝수로 만들려면 요소 하나, 즉 5를 제거해야 합니다. 5를 제거하면 나머지 요소들의 합은 10 + 20 + 30 = 60으로 짝수가 되어 조건을 만족합니다.

알고리즘

이 문제는 정수의 덧셈 성질을 활용하면 매우 간단하게 해결할 수 있습니다. 핵심 원리는 다음과 같습니다.

1. 짝수는 몇 개를 더하더라도 그 합은 항상 짝수입니다.
2. 홀수를 홀수 개만큼 더하면 그 합은 항상 홀수입니다.
3. 홀수를 짝수 개만큼 더하면 그 합은 항상 짝수입니다.
4. 따라서 배열에 포함된 홀수 요소의 개수를 세어 봅니다. 홀수 요소의 개수가 짝수라면 어떤 요소도 제거할 필요가 없으며, 홀수 요소의 개수가 홀수라면 홀수 요소 중 아무거나 하나만 제거하면 전체 합이 짝수가 됩니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;
int getMinRemovals(int *arr, int n) {
   int cnt = 0;
   for (int i = 0; i < n; ++i) {
      if (arr[i] % 2 == 1) {
         ++cnt;
      }
   }
   return (cnt % 2 == 0) ? 0 : 1;
}
int main() {
   int arr[] = {10, 20, 30, 5};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "최소 제거 횟수 = " << getMinRemovals(arr, n) << endl;
   return 0;
}

위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.

출력 결과

최소 제거 횟수 = 1

복잡도 분석

시간 복잡도: O(N) — 배열을 한 번만 순회하면서 홀수 요소의 개수를 세므로 선형 시간 안에 해결할 수 있습니다.
공간 복잡도: O(1) — 추가적인 자료구조 없이 카운터 변수 하나만 사용하므로 메모리 사용량은 일정합니다.