C++에서 2 또는 7로 나누어 떨어지는 1부터 N까지 자연수의 합 구하기

문제 소개

이번 문제에서는 하나의 정수 N이 주어졌을 때, 1부터 N 사이에서 2 또는 7로 나누어 떨어지는 모든 자연수의 합을 구하는 것이 과제입니다.

예시를 통해 문제를 이해해 보겠습니다.

입력:

N = 10

출력:

37

설명:

합계 = 2 + 4 + 6 + 7 + 8 + 10 = 37

10 이하에서 2의 배수는 2, 4, 6, 8, 10이고, 7의 배수는 7입니다. 이들을 모두 더하면 37이 됩니다.

문제 해결 접근 방식

이 문제의 핵심 아이디어는 포함-배제 원리(Inclusion-Exclusion Principle)입니다. 반복문으로 1부터 N까지 모든 수를 일일이 검사할 수도 있지만, 등차수열 공식을 활용하면 훨씬 효율적으로 답을 구할 수 있습니다.

먼저 다음 두 가지 합을 각각 구합니다.

• 2로 나누어 떨어지는 수들의 합 (S₂)
• 7로 나누어 떨어지는 수들의 합 (S₇)

그런데 14(= 2 × 7)의 배수는 위 두 합에 중복되어 포함되므로, 최종 합계는 다음과 같이 계산해야 합니다.

총합 = (2의 배수의 합) + (7의 배수의 합) − (14의 배수의 합)

1부터 N 사이의 각 배수들은 등차수열을 이루므로, 등차수열의 합 공식을 사용하면 각 합을 상수 시간에 구할 수 있습니다.

S₂ = ((N/2)/2) × (2×2 + (N/2 − 1)×2)
S₇ = ((N/7)/2) × (2×7 + (N/7 − 1)×7)
S₁₄ = ((N/14)/2) × (2×14 + (N/14 − 1)×14)

따라서 최종 합은 다음과 같습니다.

합계 = S₂ + S₇ − S₁₄

C++ 구현 예제

위 접근 방식을 구현한 프로그램입니다.

#include <iostream>
using namespace std;

int findSum(int N) {
    return ( ((N/2)*(2*2+(N/2-1)*2)/2)
           + ((N/7)*(2*7+(N/7-1)*7)/2)
           - ((N/14)*(2*14+(N/14-1)*14)/2) );
}

int main() {
    int N = 42;
    cout << "2 또는 7로 나누어 떨어지는 자연수의 합: " << findSum(N);
    return 0;
}

실행 결과

2 또는 7로 나누어 떨어지는 자연수의 합: 525

N = 42일 때, 2의 배수의 합은 462, 7의 배수의 합은 147, 14의 배수의 합은 84입니다. 따라서 462 + 147 − 84 = 525가 되어 프로그램의 출력과 일치합니다.

복잡도 분석

시간 복잡도: O(1) — 반복문 없이 등차수열 공식만으로 계산하므로 N의 크기와 무관하게 일정한 시간 안에 결과를 얻을 수 있습니다.

공간 복잡도: O(1) — 추가적인 메모리를 사용하지 않습니다.