ProjectEuler 풀이 - Problem 6. Sum square difference

Project Euler에 있는 재미있는 문제를 하나 풀었습니다.

6번째 문제로 제목은 Sum square difference 입니다.

The sum of the squares of the first ten natural numbers is,

1² + 2² + ... + 10² = 385

The square of the sum of the first ten natural numbers is,

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

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025  385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

1부터 100까지 각 숫자의 제곱의 합에서 1부터 100까지 더한 수의 제곱을 빼면 얼마인지 묻는 문제입니다.

일단 무식하게 for문을 돌려서 각 제곱의 합을 구하고, 

또한 매 루프마다 더한 sum을 제곱하면 될 것 같습니다.

하지만 100까지가 아니라 더 큰 수까지의 값을 구하라고 하면 integer의 범위를 넘어가 버리기 때문에 다른 방법이 필요합니다.

그리고 알고리즘 문제니까 뭔가 속도도 빠르게 할 수 있는 방법이 있을 것입니다.

저는 이렇게 풀어 보았습니다.

(a+b) = a² + b² + 2ab 이므로, 

이렇게 됩니다.

각 숫자의 제곱 부분을 좌항으로 옮기면 남는 부분이 결국 우리가 구하고자 하는 값입니다.

각 부분에 포함된 2를 앞으로 묶어 내면 뭔가 규칙이 생기네요.

n=3 일 때는 2번의 덧셈, n=4일 때는 3번의 덧셈이 됩니다.

즉 n-1번 loop를 돌리면 될 것 같습니다.

그리고 각 항에서 곱셈으로 연결된 좌측 숫자는 n-1에서 1까지 작아지고,

우측 숫자는 (좌측 숫자+1)부터 n까지 더한 값입니다.

이를 구현하면 이렇게 됩니다.

public int sumSquareDifference(int n) { if (n < 1) { return -1; }

int sum = 0; for (int i = n - 1; i > 0; i--) { int _sum = 0; for (int j = i + 1; j <= n; j++) { _sum += j; }

sum += 2 * (i * _sum); } return sum; }

정답!!

하지만 이 알고리즘의 성능은 O(n²)으로 그다지 좋지 않습니다.

Project Euler에서 제시한 정답은 단 3줄의 코딩으로 끝납니다.

성능은 O(1)입니다. loop를 쓰지도 않았다는 말입니다.

여러분도 정답을 보기 전에 다른 방법으로 한 번 풀어보시길 바랍니다. 풀이를 보면 아하! 하고 느끼실 수 있을 겁니다.

평소 문제를 접할 때에도 바로 컴퓨터 앞에서 키보드를 두들기기 전에 좀더 간단한 문제로 바꿀 수 있는 방법을 고민해 보세요.

만약 성공한다면 메모리와 수행 시간을 획기적으로 줄일 수 있을 겁니다.