배열이 주어졌을 때, 0보다 큰 최소 숫자를 배열에 더하여 배열 원소들의 합을 짝수로 만드는 문제입니다.
입력 – 1 2 3 4
출력 – 2
설명 – 배열의 합은 10으로 이미 짝수입니다. 여기에 1을 더하면 오히려 합이 홀수가 되기 때문에, 합을 짝수로 유지하면서 더할 수 있는 가장 작은 양수인 2를 더해야 합니다.
방법 1: 전체 합 계산하기
배열의 모든 원소를 더한 후 그 합을 검사합니다. 합이 짝수라면 최소 숫자는 2이고, 합이 홀수라면 최소 숫자는 1입니다.
예제
#include<iostream>
using namespace std;
int main() {
int arr[] = { 1, 2, 3, 4};
int n=4;
int sum=0;
for (int i = 0; i <n; i++) {
sum+=arr[i];
}
if (sum % 2==0) {
cout <<"2";
} else {
cout <<"1";
}
return 0;
}방법 2: 홀수 원소의 개수 세기
배열에서 홀수 원소의 개수를 셉니다. 홀수 원소의 개수가 짝수라면 전체 합도 짝수이므로 2를 반환하고, 홀수 원소의 개수가 홀수라면 전체 합도 홀수이므로 1을 반환합니다.
입력 – 1 2 3 4 5
출력 – 1
설명 – 배열 속 홀수의 개수는 3개입니다. 최소 숫자 1을 더해 합을 짝수로 만듭니다.
예제
#include<iostream>
using namespace std;
int main() {
int arr[] = { 1, 2, 3, 4,5};
int n=5;
int odd = 0;
for (int i = 0; i < n; i++) {
if (arr[i] % 2!=0) {
odd += 1;
}
}
if (odd % 2==0) {
cout <<"2";
} else {
cout <<"1";
}
return 0;
}방법 3: 플래그 변수와 NOT 연산 활용하기
플래그 변수(초깃값 0)를 하나 선언합니다. 배열을 순회하면서 홀수 원소를 발견할 때마다 불리언 변수에 NOT(!) 연산을 적용합니다. 이 논리 연산자는 플래그 변수의 값을 반전시키는데, 즉 값이 0이면 1로, 1이면 0으로 바뀝니다.
입력 – 1 2 3 4 5
출력 – 1
설명 – 변수는 0으로 초기화됩니다.
배열을 순회하면 다음과 같습니다.
1은 홀수 → 변수가 1로 변경
2는 짝수
3은 홀수 → 변수가 0으로 변경
4는 짝수
5는 홀수 → 변수가 1로 변경
변숫값이 1이라는 것은 배열에 홀수 원소가 홀수 개 있다는 뜻이며, 이 경우 원소들의 합을 짝수로 만들기 위해 더해야 하는 최소 숫자는 1입니다. 그렇지 않다면 최소 숫자는 2입니다.
예제
#include<iostream>
using namespace std;
int main() {
int arr[] = { 1, 2, 3, 4,5};
int n=5;
bool odd = 0;
for (int i = 0; i < n; i++) {
if (arr[i] % 2!=0) {
odd = !odd;
}
}
if (odd) {
cout <<"1";
} else {
cout <<"2";
}
return 0;
}정리
세 가지 방법 모두 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 동일합니다. 방법 1은 합을 직접 계산하는 직관적인 접근 방식이고, 방법 2와 3은 홀수 원소의 개수만 확인한다는 점에서 효율적입니다. 특히 방법 3은 카운트 변수 대신 플래그 하나만 사용하므로 메모리 사용 측면에서 가장 깔끔한 구현입니다.