티스토리 뷰

Project Euler

프로젝트 오일러

 

Problem 6

'합의 제곱'에서 '제곱의 합'을 뺀 값 구하기

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

1^2 + 2^2 + ... + 10^2 = 385

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

(1 + 2 + ... + 10)^2 = 55^2 = 3025

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

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


Hint

등차수열의 합 공식!


등차수열이란?

연속하는 두 항의 차이가 모두 일정한 수열을 뜻한다. 예를 들어 1, 2, 3, 4, 5, ... 혹은 1, 3, 5, 7, 9, ... 모두 등차수열이라고 한다.


등차수열의 합 공식


2번공식은 "제곱의 합"에 해당합니다!

1^2 + 2^2 + ... 그럼 제곱의 합을 구할 땐 저 공식을 이용합니다.


다음 "합의 제곱"은 1번 공식을 사용합니다.

1번 공식은 1+2+3+4+...+10을 의미합니다.

이 1번 공식을 제곱하면 "합의 제곱"을 구할 수 있는 것이죠.


Answer

저는 공식을 이용해서 다음과 같이 풀었습니다.

sumOfSquares : 제곱의 합

squareOfSum : 합의 제곱

public static int Problem06(int mainNum){
int sumOfSquares = (mainNum * (mainNum+1) * ((2*mainNum)+1))/6;
int squareOfSum = (((mainNum * (mainNum+1))/2)) * (((mainNum * (mainNum+1))/2));
return (squareOfSum - sumOfSquares);
}


다음과 같이 푸신 분들도 있더라구요.

위에 힌트의 3번 공식을 적용한 방법입니다.

"합의 제곱"은 결국 1^3 + 2^3 + 3^3 + ... + 100^3 이렇게 세제곱 등차수열의 합이 되기 때문입니다.

public static int Problem06_OtherCase(){
int i1 = 0 ;
int i2 = 0 ;

for(int i = 1 ; i <= 100 ; i++){
i1 = i1 + (int)Math.pow(i, 2);
i2 = i2 + (int)Math.pow(i, 3);
}

return (i2 - i1);
}



댓글
댓글쓰기 폼
공지사항
Total
41,170
Today
70
Yesterday
59
링크
TAG
more
«   2018/07   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        
글 보관함