Project Euler. #6. Sum square difference

By | 2013/02/18

Project Euler (http://projecteuler.net/) 문제6

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

12 + 22 + ... + 102 = 385

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

(1 + 2 + ... + 10)2 = 552 = 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에서 10까지의 자연수의 제곱들의 합은,

12 + 22 + ... + 102 = 385

1에서 10까지의 자연수의 합의 제곱은,

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

여기서 이 수들의 합의 제곱과 제곱의 합의 차이는 3025 - 385 = 2640 이다.

1에서 100까지의 자연수의 합의 제곱과 제곱의 합의 차이를 구하여라.


#My Solution 1
sumOfSqr = 0
sqrOfSum = 0
for i in range(1,101):
    sumOfSqr += i*i
    sqrOfSum +=i
print (sqrOfSum*sqrOfSum)-sumOfSqr


#My Solution 2
print sum([j for j in range(1,101)])**2 - sum([i*i for i in range(1,101)])

이번 문제는 이전 문제들에 비해 매우 간단하게 풀 수 있었다. 처음에 My Solution 1 소스와 같이 해결했다가 심심한데 소스 길이나 줄여보자 해서 또 리스트 내장을 이용해서 코드를 짧게 줄일 수 있었다. 다른 사람들이 짠 파이썬 코드를 부니 대부분이 위의 두 코드와 매우 흡사했는데, 간단하면서도 볼만한 소스를 하나 찾았다.


# Developed by skarr on Project Euler
import itertools
print sum([x*y*2 for (x,y) in itertools.combinations(range(1,101),2)])

기가 막히는 방법이다. itertools 모듈의 combinations 함수(http://docs.python.org/2/library/itertools.html#itertools.combinations)를 잘 활용하였다. combination 함수는 2개의 파라미터 iterable, r을 받는다. 즉, combination(iterable, r)은 iterable 에서 r개를 뽑을 수 있는 모든 경우의 수를 반환한다. 그러므로 위 코드는 1에서 100까지의 숫자 중 2개를 뽑을 수 있는 모든 경우의 수를 (x,y)에 넘기고, x*y*2의 값들로 이루어진 리스트의 합을 출력한다. (a+b+c)2은 a2+b2+c2+2ab+2ac+2bc 이므로 위와 같이 계산하는 것이 가능했다. 물론 import 문 때문에 내가 코딩한 한 줄짜리 답보다 라인 수가 한 줄 더 길긴 하지만 문제 해결 접근법은 나보다 한 수 위인 해결 방법이다.

문제가 쉽다고 방심 했는데, 이런 재밌는 해결 방법이 있을거라고는 생각도 하지 못했다. 이렇게 Proejct Euler의 문제를 통해 나의 부족함을 느끼는 것과 이를 인정하고 성장해나가는 과정의 반복되고 있구나.