C++로 처음 n개의 자연수의 m번째 합 구하기

이 문제에서는 두 개의 정수 m과 n이 주어지며, 우리의 과제는 처음 n개의 자연수에 대한 m번째 합(m-th summation)을 구하는 것입니다.

문제 설명

n개의 자연수의 합을 m번 반복해서 누적한 값을 구해야 합니다. 즉, 이전 단계에서 구한 합을 다시 자연수의 합 공식에 대입하는 방식으로 계산이 이루어집니다. 수식으로 표현하면 다음과 같습니다.

m > 1인 경우:

sum(n, m) = sum( sum(n, m-1), 1 )

m = 1인 경우:

sum(n, m) = sum(n, 1) = n개의 자연수의 합

예제로 문제 이해하기

입력: m = 4, n = 2

출력: 231

설명:

sum(2, 4) = sum( sum(2, 3), 1 )
= sum( sum( sum(2, 2), 1 ), 1 )
= sum( sum( sum( sum(2, 1), 1 ), 1 ), 1 )
= sum( sum( sum(3, 1), 1 ), 1 )
= sum( sum(6, 1), 1 )
= sum(21, 1)
= 231

풀이 접근 방법

가장 간단한 해결 방법은 두 개의 중첩 반복문을 사용하는 것입니다. 바깥쪽 반복문은 m을 처리하고, 안쪽 반복문은 n값을 이용해 합을 계산합니다. 매번 n의 값을 갱신하면서 자연수의 합을 m번 계산하면 됩니다.

하지만 더 효율적인 방법은 재귀 호출을 활용하는 것입니다. 재귀가 호출될 때마다 이전 단계에서 구한 합으로 값을 갱신하며, 자연수의 합 공식을 m번 적용합니다.

알고리즘

1단계: m이 1보다 크면, sum 값을 다음과 같이 갱신합니다.
sum = sum(n, m-1) * (sum(n, m-1) + 1) / 2

2단계: m = 1이면, 기본 공식을 반환합니다.
sum = n * (n + 1) / 2

3단계: 최종 sum 값을 반환합니다.

C++ 구현 예제

아래 프로그램은 위에서 설명한 풀이 방식이 실제로 어떻게 동작하는지 보여줍니다.

#include <iostream>
using namespace std;

int calcSumN(int n, int m) {
    if (m == 1)
        return (n * (n + 1) / 2);
    return (calcSumN(n, m-1) * (calcSumN(n, m-1) + 1) / 2);
}

int main() {
    int n = 4;
    int m = 6;
    cout<<m<<"-th summation of first "<<n<<" natural numbers is "<<calcSumN(n, m);
    return 0;
}

실행 결과

6-th summation of first 4 natural numbers is 125230148

위 코드에서는 n = 4, m = 6일 때 재귀적으로 합을 계산하여 결과를 출력합니다. 재귀 함수 calcSumN은 m이 1이 될 때까지 자기 자신을 호출하면서, 각 단계마다 이전 결과에 자연수의 합 공식 n*(n+1)/2를 적용합니다. 이러한 방식은 중첩 반복문을 사용하는 방법보다 코드가 간결하고 로직이 명확하다는 장점이 있습니다.