C 언어로 처음 n개의 자연수의 세제곱합 구하기: 반복문과 수식 활용법

이번 문제에서는 처음 n개의 자연수의 세제곱합(1³ + 2³ + 3³ + ... + n³)을 구하는 방법을 알아보겠습니다.

가장 기본적인 접근 방법은 1부터 n까지 반복하는 for 루프를 사용하는 것입니다. 각 단계마다 해당 항의 세제곱을 계산한 후 누적 합계에 더해주면 됩니다. 이 방법은 시간 복잡도가 O(n)으로, n이 커질수록 실행 시간이 비례하여 늘어납니다.

하지만 O(1), 즉 상수 시간에 문제를 해결하고 싶다면 다음과 같은 수열 공식을 활용할 수 있습니다.

처음 n개의 자연수의 세제곱합 = [n(n+1)/2]²

알고리즘

cubeNNatural(n)

begin
    sum := 0
    for i in range 1 to n, do
        sum := sum + i^3
    done
    return sum
end

C 언어 구현 예제

#include<stdio.h>
long cube_sum_n_natural(int n) {
    long sum = 0;
    int i;
    for (i = 1; i <= n; i++) {
        sum += i * i * i; // i의 세제곱을 계산하여 합계에 더함
    }
    return sum;
}
main() {
    int n;
    printf("Enter value of n: ");
    scanf("%d", &n);
    printf("Result is: %ld", cube_sum_n_natural(n));
}

실행 결과

Enter value of n: 6
Result is: 441

n이 6일 때 결과는 441입니다. 실제로 1³ + 2³ + 3³ + 4³ + 5³ + 6³ = 1 + 8 + 27 + 64 + 125 + 216 = 441로 확인할 수 있습니다.

참고로 위 공식을 이용하면 [6 × 7 / 2]² = 21² = 441로 동일한 결과를 한 번의 계산으로 얻을 수 있습니다. 입력 크기가 매우 큰 경우에는 반복문 대신 수식 기반 접근이 훨씬 효율적입니다.