별의 공부 블로그 🧑🏻‍💻
728x90
728x170

문제6: 1부터 100까지 "제곱의 합"과 "합의 제곱"의 차는?


문제


1부터 10까지 자연수를 각각 제곱해 더하면 다음과 같습니다 (제곱의 합).

12+22+...+102=385

1부터 10을 먼저 더한 다음에 그 결과를 제곱하면 다음과 같습니다 (합의 제곱).

(1+2+...+10)2=552=3025

따라서 1부터 10까지 자연수에 대해 "합의 제곱"과 "제곱의 합" 의 차이는 3025 - 385 = 2640 이 됩니다.

그러면 1부터 100까지 자연수에 대해 "합의 제곱"과 "제곱의 합"의 차이는 얼마입니까?


문제 해결 방법


하나하나씩 계산하는 방식(브루트 포스 방식)으로 문제를 해결하였다.
  • for문을 사용하여
    • 자연수 1부터 N(100)까지의 합을 numOfSum 변수에 할당하였다.
    • 자연수 1의 제곱부터 N(100)의 제곱까지의 합을 numOfTimes 변수에 할당하였다.
      • <cmath> 헤더를 불러와 pow() 함수 사용
  • for문을 빠져 나오면 numOfSum 변수의 값과 numOfSum 변수의 값을 곱한 값을 numOfSum 변수에 할당하였다.
  • numOfSum 변수의 값과 numOfTimes 변수의 값의 차의 절댓값을 ans 변수에 할당하여 출력하도록 하였다.
    • <cmath> 헤더의 abs() 함수 사용

소스 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cmath>
using namespace std;
 
#define N 100
 
int main() {
    int numOfSum = 0, numOfTimes = 0, ans;
 
    for (int i = 1; i <= N; i++) {
        numOfSum += i;
        numOfTimes += pow(i, 2);
    }
    numOfSum *= numOfSum;
 
    ans = abs(numOfSum - numOfTimes);
    cout << ans << endl;
 
    return 0;
}



정답


 25164150


심화 공부


거듭제곱의 합 공식(Faulhaber's Formula)


처음 n개 자연수의 p거듭제곱의 합은 (p+1)차 다항식으로 표현될 수 있다.

nk=1kp=1p+2p+3p++np=np+1p+1+12np+pk=2Bkk!pk1–––npk+1,

처음 몇 가지  예는 아래와 같다:

1+2+3++n=n(n+1)2=n2+n2

12+22+32++n2=n(n+1)(2n+1)6=2n3+3n2+n6

13+23+33++n3=[n(n+1)2]2=n4+2n3+n24

14+24+34++n4=n(n+1)(2n+1)(3n2+3n1)30=6n5+15n4+10n3n30

15+25+35++n5=[n(n+1)]2(2n2+2n1)12=2n6+6n5+5n4n212

16+26+36++n6=n(n+1)(2n+1)(3n4+6n33n+1)42=6n7+21n6+21n57n3+n42

이 공식을 독일 수학자 파울하버(Johann Faulhaber) 의 이름을 따서 파울하버 공식 또는 스위스 수학자 베르누이(Jacob Bernoulli) 의 이름을 따서 베르누이 공식 이라고도 부른다.




728x90
그리드형(광고전용)


📖 Contents 📖
문제6: 1부터 100까지 "제곱의 합"과 "합의 제곱"의 차는?문제문제 해결 방법소스 코드정답심화 공부거듭제곱의 합 공식(Faulhaber's Formula)