C++로 N 이하 자연수 중 K로 나눈 나머지가 R인 수들의 합 구하기

이 문제에서는 세 개의 수 N, K, R이 주어집니다. 우리의 목표는 N 이하의 자연수 중에서 K로 나누었을 때 나머지가 R이 되는 수들을 모두 찾아 그 합을 구하는 프로그램을 작성하는 것입니다.

즉, 다음 조건을 만족하는 N 이하의 모든 수를 더하면 됩니다.

i % K == R

문제 이해를 위한 예시

입력

N = 14, K = 4, R = 1

출력

28

설명 — 14 이하의 수 중에서 4로 나누었을 때 나머지가 1이 되는 수는 1, 5, 9, 13입니다. 이 수들을 모두 더하면 1 + 5 + 9 + 13 = 28이 됩니다.

해결 접근 방법

이 문제를 효율적으로 해결하려면 R부터 시작하여 N까지 K씩 값을 증가시키며 반복문을 실행하면 됩니다. 이렇게 하면 조건을 만족하는 모든 수를 빠짐없이 순회할 수 있고, 해당 값들을 합계에 더해가면 됩니다.

물론 간격을 1로 하는 일반적인 반복문을 사용해도 결과는 같지만, K씩 건너뛰며 순회하는 방식이 불필요한 반복을 줄여 실행 시간을 크게 단축할 수 있습니다.

구현 예제

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

#include <iostream>
using namespace std;

int CalcSumofRem(int N, int K, int R) {
    int sum = 0;
    for (int i = R; i <= N; i += K) {
        if (i % K == R)
            sum += i;
    }
    return sum;
}

int main() {
    int N = 14, K = 4, R = 1;
    cout << "Sum of natural numbers (up to " << N << ") whose modulo with " << K << " yields " << R << " is " << CalcSumofRem(N, K, R);
    return 0;
}

출력 결과

Sum of natural numbers (up to 14) whose modulo with 4 yields 1 is 28

추가 최적화: 등차수열 공식 활용

조건을 만족하는 수들은 R, R+K, R+2K, ... 형태의 등차수열을 이루므로, 반복문 없이 수학 공식으로도 합을 구할 수 있습니다.

int CalcSumofRemFormula(int N, int K, int R) {
    if (R > N) return 0;
    int count = (N - R) / K + 1;          // 조건을 만족하는 수의 개수
    return count * (2 * R + (count - 1) * K) / 2;  // 등차수열의 합 공식
}

이 방법은 O(1)의 시간 복잡도로 동작하므로 N이 매우 클 때 특히 유용합니다. 반복문 기반 풀이의 시간 복잡도는 O(N/K)입니다.