[Project Euler #6][C++] 1부터 100까지 "제곱의 합"과 "합의 제곱"의 차는?
Problem Solving/Project Euler 2020. 12. 22. 20:54728x90
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!pk−1–––––np−k+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+3n−1)30=6n5+15n4+10n3−n30
15+25+35+⋯+n5=[n(n+1)]2(2n2+2n−1)12=2n6+6n5+5n4−n212
16+26+36+⋯+n6=n(n+1)(2n+1)(3n4+6n3−3n+1)42=6n7+21n6+21n5−7n3+n42
이 공식을 독일 수학자 파울하버(Johann Faulhaber) 의 이름을 따서 파울하버 공식 또는 스위스 수학자 베르누이(Jacob Bernoulli) 의 이름을 따서 베르누이 공식 이라고도 부른다.
728x90
그리드형(광고전용)
'Problem Solving > Project Euler' 카테고리의 다른 글
[Project Euler #10][C++]이백만 이하 소수의 합 (0) | 2020.12.24 |
---|---|
[Project Euler #9][C++] a + b + c = 1000 이 되는 피타고라스 수 (0) | 2020.12.23 |
[Project Euler #8][C++] 1000자리 수 안에서 이어지는 5개 숫자의 곱 중 최댓값은? (0) | 2020.12.22 |
[Project Euler #7][C++] 10001번째의 소수 (0) | 2020.12.22 |
[Project Euler #5][C++] 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수 (0) | 2020.11.16 |
[Project Euler #4][C++] 세자리 수를 곱해 만들 수 있는 가장 큰 대칭수 (0) | 2020.11.15 |
[Project Euler #3][C++] 가장 큰 소인수 구하기 (0) | 2020.10.26 |
[Project Euler #2][C++] 피보나치 수열에서 4백만 이하이면서 짝수인 항의 합 (0) | 2020.10.24 |