C++로 배열 합을 홀수로 만들기 위해 제거해야 하는 최소 원소 개수 구하기

문제 설명

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

예시

입력 배열이 {10, 20, 30, 5, 7}이라면, 배열의 전체 합은 72(짝수)입니다. 이때 원소 중 하나인 5 또는 7만 제거하면 나머지 원소들의 합이 홀수가 되므로, 최소 제거 횟수는 1입니다.

알고리즘

이 문제는 수학적 성질을 이용하면 매우 간단하게 해결할 수 있습니다.

1. 짝수는 몇 개를 더해도 그 합은 항상 짝수입니다.
2. 홀수를 홀수 번 더하면 그 합은 항상 홀수입니다.
3. 홀수를 짝수 번 더하면 그 합은 항상 짝수입니다.
4. 따라서 배열에 포함된 홀수 원소의 개수를 셉니다.
   - 홀수 원소의 개수가 짝수이면 → 원소 1개를 제거해야 합니다.
   - 홀수 원소의 개수가 홀수이면 → 아무것도 제거할 필요가 없습니다.

참고로, 배열에 홀수 원소가 하나도 없다면 어떤 원소를 제거하더라도 합을 홀수로 만들 수 없습니다. 다만 본 문제에서는 홀수 원소가 존재한다고 가정합니다.

예제 코드

#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) ? 1 : 0;
}
int main() {
    int arr[] = {10, 20, 30, 5, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "최소 제거 횟수 = " <<
    getMinRemovals(arr, n) << endl;
    return 0;
}

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

출력 결과

최소 제거 횟수 = 1

이 알고리즘의 시간 복잡도는 O(N), 공간 복잡도는 O(1)로, 배열을 한 번만 순회하면 되기 때문에 매우 효율적입니다.