정수의 '합의 합(sum of sum)'을 구하는 개념은 다음과 같습니다. 먼저 1부터 n까지 각 숫자에 대한 누적 합을 구한 뒤, 이 값들을 모두 더하여 최종 결과를 얻는 방식입니다.
이 문제에서는 하나의 수 n이 주어지며, 1부터 n까지 각 숫자까지의 합을 다시 모두 더한 값을 계산해야 합니다. n = 4인 경우를 예로 살펴보겠습니다.
n = 4
1부터 4까지 각 숫자까지의 합을 구하면 다음과 같습니다.
1까지의 합 = 1
2까지의 합 = 1 + 2 = 3
3까지의 합 = 1 + 2 + 3 = 6
4까지의 합 = 1 + 2 + 3 + 4 = 10
이제 위의 값들을 모두 더하면 원하는 결과를 얻을 수 있습니다.
합의 합 = 1 + 3 + 6 + 10 = 20
처음 n개의 자연수 합의 합을 구하는 방법은 두 가지가 있습니다.
- 방법 1 - for 루프 사용 (비효율적)
- 방법 2 - 수학 공식 사용 (효율적)
방법 1 - for 루프 사용하기
이 방법에서는 두 개의 for 루프를 사용합니다. 안쪽 루프는 각 숫자 i까지의 자연수 합을 계산하고, 바깥쪽 루프는 그 합을 총합 변수에 더한 뒤 다음 숫자로 넘어갑니다. 각 반복마다 내부 합계 변수를 반드시 초기화해주어야 올바른 결과를 얻을 수 있습니다.
예제 코드
#include <stdio.h>
int main() {
int n = 4;
int sum = 0, s;
for(int i = 1; i <= n; i++){
s = 0;
for(int j = 1; j <= i; j++){
s += j;
}
sum += s;
}
printf("처음 %d개 자연수 합의 합은 %d입니다", n, sum);
return 0;
}
출력 결과
처음 4개 자연수 합의 합은 20입니다
방법 2 - 수학 공식 사용하기
반복문 없이 수학 공식 하나만으로 결과를 즉시 계산할 수 있기 때문에, 공식을 활용하는 방법이 훨씬 효율적입니다.
처음 n개의 자연수 합의 합을 구하는 수학 공식은 다음과 같습니다.
sum = n * (n + 1) * (n + 2) / 6
이 공식은 사면체수(tetrahedral number) 공식으로, 1부터 n까지의 합 n(n+1)/2를 다시 1부터 n까지 모두 더한 값과 같습니다. n = 4인 경우 4 × 5 × 6 ÷ 6 = 20으로, 앞서 루프로 구한 결과와 정확히 일치합니다.
예제 코드
#include <stdio.h>
int main() {
int n = 4;
int sum = (n * (n + 1) * (n + 2)) / 6;
printf("처음 %d개 자연수 합의 합은 %d입니다", n, sum);
return 0;
}
출력 결과
처음 4개 자연수 합의 합은 20입니다
두 방법의 비교
방법 1은 중첩 루프를 사용하기 때문에 시간 복잡도가 O(n²)로, n이 커질수록 실행 속도가 크게 느려집니다. 반면 방법 2는 단순한 산술 연산만 수행하므로 O(1)의 상수 시간에 결과를 구할 수 있습니다. 따라서 실제 개발 환경에서는 수학 공식을 활용하는 방법 2를 사용하는 것이 좋습니다.