C++로 합이 짝수인 비어 있지 않은 부분 집합의 길이 찾기

문제 개요

n개의 요소를 가진 배열 A가 주어졌을 때, 요소들의 합이 짝수가 되는 비어 있지 않은 부분 집합(subset)의 길이를 구해야 합니다. 만약 조건을 만족하는 부분 집합이 존재하지 않는다면 -1을 반환합니다.

예를 들어 입력이 A = [1, 3, 7]이라면 출력은 2가 됩니다. 그 이유는 [1, 3]의 합이 4로 짝수이기 때문입니다.

해결 접근 방식

이 문제는 배열에 포함된 숫자들의 홀짝성(짝수 또는 홀수 여부)만 확인하면 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 배열에 짝수가 하나라도 있는 경우: 그 짝수 하나만 선택해도 합이 짝수가 되므로, 길이 1의 부분 집합이 성립합니다.
• 모든 요소가 홀수인 경우: 홀수 두 개를 더하면 짝수가 되므로, 길이 2의 부분 집합을 선택하면 됩니다.
• 예외 경우: 배열의 크기가 1이면서 유일한 요소가 홀수라면, 조건을 만족하는 부분 집합이 존재하지 않으므로 -1을 반환합니다.

이 논리를 의사 코드로 표현하면 다음과 같습니다.

n := A의 크기
i := 0으로 초기화, i < n인 동안 i를 1씩 증가시키며 반복:
    if A[i] mod 2 == 0 then:
        k := i + 1
if n == 1 AND k == 0 then:
    return -1
else if k != 0 then:
    return 1
otherwise:
    return 2

C++ 구현 예제

아래 구현 예제를 통해 동작 방식을 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A) {
    long n = A.size(), k = 0;
    for (long i = 0; i < n; i++) {
        if (A[i] % 2 == 0) {
            k = i + 1;
        }
    }
    if (n == 1 && k == 0) {
        return -1;
    }
    else if (k != 0) {
        return 1;
    }
    else {
        return 2;
    }
}
int main() {
    vector<int> A = { 1, 3, 7 };
    cout << solve(A) << endl;
}

입력

{ 1, 3, 7 }

출력

2

코드 설명

주어진 입력 { 1, 3, 7 }에는 짝수가 하나도 없습니다. 따라서 변수 k는 0으로 유지되고, 배열의 크기는 3이므로 마지막 분기문에 따라 2가 반환됩니다. 이는 홀수 두 개(예: 1과 3)를 선택하여 합이 짝수(4)가 되는 부분 집합을 만들 수 있다는 의미입니다.

이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리 사용 없이 상수 공간 O(1)로 해결할 수 있습니다. 배열의 크기와 관계없이 효율적으로 동작하는 장점이 있습니다.