Project Euler #6

Project Euler #6

---

• 문제
  
  • 풀이 1
  • 풀이 2
• 후기

문제

---

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

$1^2 + 2^2 + ... + 10^2 = 385$
The square of the sum of the first ten natural numbers is,

$(1 + 2 + ... + 10)^2 = 55^2 = 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.

처음 10개 자연수의 제곱의 합은 다음과 같다.

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

처음 10개 자연수의 합의 제곱은 다음과 같다.

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

처음 10개 자연수에 대한 합의 제곱과 제곱의 합의 차는 다음과 같다.

$3025 − 385 = 2640$

처음 100개 자연수에 대한 합의 제곱과 제곱의 합의 차를 구하라.

풀이 1

---

• 일차원적으로 접근하면 다음과 같다.
• sum함수를 이용했다.

import time
num = 100
stime = time.time()

sumS = sum(range(1, num + 1)) ** 2
Ssum = sum(x ** 2 for x in range(1, num + 1))

print(sumS - Ssum)
print("Running Time: %f" %(time.time() - stime))

풀이 2

---

• 앞서 말한 것과 같이 풀이 1은 일차원적으로 접근한 풀이법이다.
• 사실 100까지의 자연수기 때문에 크게 수행속도 면에서 차이는 없으나 좀 더 효율적인 방법을 제시해 보고자 한다.
• 1부터 n까지의 합은 $\displaystyle \sum_{k=1}^{n}k = \frac{n(n + 1)}{2}$ 이다.
• $1^2$부터 $n^2$까지의 합의 공식 유도 과정 다음과 같다.(제곱의 합)

$$\begin{matrix} (x + 1)^3 & = & (x^2 + 2x + 1)(x + 1) \\ & = & (x^3 + 2x^2 + x) + (x^2 + 2x + 1) \\ & = & x^3 + 3x^2 + 3x + 1 \end{matrix} \\ \therefore \quad (x + 1)^3 - x^3 = 3x^2 + 3x + 1 \\ \text{위의 } (x + 1)^3 \text{의 전개식을 변형하여 이용한다.} \\ \begin{matrix} & x = 1 \to & \cancel{2^3} - 1^3 & = 3*1^2 + 3*1 +1 \\ & x = 2 \to & \cancel{3^3} - \cancel{2^3} & = 3*2^2 + 3*2 +1 \\ & x = 3 \to & \cancel{4^3} - \cancel{3^3} & = 3*3^2 + 3*3 +1 \\ & & \cdots & \\ + & x = n \to & (n + 1)^3 - \cancel{n^3} & = 3*n^2 + 3*n +1 \end{matrix} \\ \overline{\begin{matrix} (n + 1)^3 - 1^3 & = & \displaystyle 3\sum_{k=1}^{n}k^2 + 3\sum_{k=1}^{n}k + n \\ (n^3 + 3n^2 + 3n + 1) - 1 & = & \displaystyle 3\sum_{k=1}^{n}k^2 + 3 \times \frac{n(n + 1)}{2} + n \\ \displaystyle 3\sum_{k=1}^{n}k^2 & = & \displaystyle n^3 + 3n^2 + 3n - (3 \times \frac{n(n + 1)}{2} + n) \\ & = & \displaystyle n^3 + 3n^2 + 3n - \frac{3n^2 + 3n}{2} - n \\ & = & \displaystyle \frac{ 2n^3 + 6n^2 + 4n - 3n^2 - 3n}{2} \\ & = & \displaystyle \frac{ 2n^3 + 3n^2 + n}{2} \\ & = & \displaystyle \frac{ n(2n^2 + 3n + 1)}{2} \\ & = & \displaystyle \frac{ n(2n^2 + 2n + n + 1)}{2} \\ & = & \displaystyle \frac{ n(2n(n + 1) + (n + 1))}{2} \\ & = & \displaystyle \frac{ n(2n + 1)(n + 1)}{2} \\ \therefore \quad \displaystyle \sum_{k=1}^{n}k^2 & = & \displaystyle \frac{ n(2n + 1)(n + 1)}{6} \end{matrix}}$$

import time
num = 100
stime = time.time()

sumS = pow((num * (num + 1) / 2), 2)
Ssum = num * (2 * num + 1) * (num + 1) / 6

print(sumS - Ssum)
print("Running Time: %f" %(time.time() - stime))

후기

해당문제에서 풀이 1과 풀이 2의 수행속도 차이는 없다.

다만, 앞서 보았던 시간복잡도와 관련하여 개선의 여지가 있어 풀이 2의 형태를 추가하였다.

또한, Project Euler 자체가 수학적인 성찰을 포함하므로 풀이 2가 좀 더 의미에 부합한다고 볼 수 있다.