프로젝트 오일러 001
❓10보다 작은 자연수 중에서 3 또는 5의 배수는 3, 5, 6, 9이고, 이것을 모두 더하면 23입니다. 1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면 얼마일까요?
사실 이 문제는 문법만 알면 풀 수 있는 쉬운 문제이고, 풀 수 있는 방법이 아주 여러 가지입니다. 공차수열의 합을 구하는 공식을 사용할 수도 있고, 1,000까지 밖에 안되는 자연수가 대상이므로 루프를 돌면서 더해도 됩니다. 혹은 3 혹은 5의 배수의 집합을 만든 후 합계를 내는 방법도 있고요.
간단한 것부터 해보죠.
total = 0
for n in range(1, 1001):
if n % 3 == 0 or n % 5 == 0:
total += n
print(n)누구나 생각할 수 있는 방법이고, 사실 어느 언어로도 구현할 수 있는 방법입니다. 그렇지만 파이썬에서는 단순 합계를 구하기 위해서는 이런 식으로 루프를 돌지는 않습니다. 대신에 리스트 축약(list comprehension, 지능형 리스트라고도 부릅니다)이라는 문법을 사용해서 3 혹으 5의 배수의 리스트를 만든 것을 선호합니다. 3이나 5의 배수의 리스트가 있다면 간단히 sum() 함수를 사용해서 합계를 내고 출력하면 됩니다.
print(sum([n for n in range(1, 1001) if x % 3 == 0 || x % 5 == 0]))등차수열의 합은 공식을 사용하면 반복해서 연산하지 않아도 됩니다. 다만 3의 배수의 합과 5의 배수의 합을 단순히 더하기만 하면 15의 배수들은 두 번씩 더한 셈이 되기 때문에 빼줘야 합니다.
print(
(3 + 999) * ((999 - 3) // 3 + 1) // 2 +\
(5 + 995) * ((995 - 5) // 5 + 1) // 2 -\
(13 + 985) * ((985 - 5) // 5 + 1) // 2
)공식은 반복적으로 사용하는 코드이기 때문에 함수로 만드는 것이 더 읽기 편합니다.
nsum = lambda x, y: (x + y) * ((y - x) // x + 1) // 2
print(nsum(3, 999) + nsum(5, 995) - nsum(15, 985))그런데 공식을 이용하는 방식에서는 끝 값을 정확하게 알아야 답이 정확하게 나옵니다. 대충 1000으로 넣으면 1000보다 작거나 같은 가장 큰 x의 배수를 끝값으로 만들도록 하면 좀 더 편하겠죠.
def nsum(start: int, end: int) -> int:
end = start * (end // start)
return (start + end) * ((end - start) // start + 1) // 2
print(nsum(3, 1000) + nsum(5, 1000) - nsum(15, 1000))이렇게 하고나니 짧고 간단한 코드가 멋져보이고, 공식을 사용하는 것이 더 번거로워 보일 수도 있습니다. 어느 쪽이든 엔터키만 탁 누르면 곧바로 답이 나오니까요. 하지만 한계값이 1,000이 아니고 10,000,000,000 정도면 어떨까요?
