문제 소개
양의 정수로 이루어진 크기 N의 배열 Arr[]가 주어집니다. 목표는 배열 요소 중 같은 소수를 반복해서 더한 합으로 표현할 수 있는 숫자가 몇 개인지 세는 것입니다. 예를 들어 4 = 2 + 2, 6 = 3 + 3 또는 2 + 2 + 2처럼 하나의 소수만으로 특정 수를 만들 수 있다면 그 숫자는 조건을 만족합니다.
이 문제의 핵심 관찰은 다음과 같습니다.
- 홀수 소수끼리의 합, 또는 짝수 소수끼리의 합은 항상 짝수가 됩니다.
- 짝수 소수는 2가 유일하므로, 2를 계속 더하면 4 이상의 모든 짝수를 표현할 수 있습니다.
- 결국 0과 2를 제외한 모든 짝수가 조건을 만족합니다.
예제로 이해하기
예제 1
입력:
Arr[] = { 2, 5, 10, 15, 20, 25 }
출력:
Number which satisfy condition : 3
설명:
Arr[0] = 2 : X → count = 0 Arr[1] = 5 : X → count = 0 Arr[2] = 10 : 5 + 5 → count = 1 Arr[3] = 15 : X → count = 1 Arr[4] = 20 : 5 + 5 + 5 + 5 → count = 2 Arr[5] = 25 : X → count = 2
예제 2
입력:
Arr[] = { 0, 2, 4, 11, 13 }
출력:
Number which satisfy condition : 1
설명:
Arr[0] = 0 : X → count = 0 Arr[1] = 2 : X → count = 0 Arr[2] = 4 : 2 + 2 → count = 1 Arr[3] = 11 : X → count = 1 Arr[4] = 13 : X → count = 1
접근 방법
아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.
- 길이 N인 양의 정수 배열을 입력으로 받습니다.
- 함수
sumofparityPrimes(int arr[], int n)는 배열과 크기를 인자로 받아, 조건을 만족하는 요소의 개수를 반환합니다. - 결과를 저장할 변수
count를 0으로 초기화합니다. - for 루프를 사용해 배열을 처음부터 끝까지 순회합니다.
- 각 요소가 짝수인지 검사합니다(
arr[i] % 2 == 0). - 짝수라면 0도 아니고 2도 아닌지 확인하고, 두 조건을 모두 통과하면
count를 1 증가시킵니다. - 루프가 종료되면
count를 결과로 반환합니다.
이 방법은 배열을 한 번만 순회하므로 시간 복잡도는 O(N)이며, 추가로 필요한 공간은 O(1)입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int sumofparityPrimes(int arr[], int n) {
int count = 0;
for (int i = 0; i < n; i++) {
if (arr[i] % 2 == 0) { // 짝수인 경우만 검사
if (arr[i] != 0) {
if (arr[i] != 2) {
count++; // 0도 2도 아니면 카운트 증가
}
}
}
}
return count;
}
int main() {
int Arr[] = { 12, 5, 15, 8, 100, 40 };
int Length = sizeof(Arr) / sizeof(Arr[0]);
cout << endl << "Number which satisfy condition : " << sumofparityPrimes(Arr, Length);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Number which satisfy condition : 4
배열 { 12, 5, 15, 8, 100, 40 }에서 짝수이면서 0과 2가 아닌 값은 12, 8, 100, 40의 네 개입니다. 이 값들은 모두 2를 반복해서 더한 형태(예: 8 = 2 + 2 + 2 + 2)로 표현할 수 있으므로 최종 결과는 4가 됩니다.