https://github.com/jongfeel/ProjectEuler/tree/master/Problems/Problem1

우연히 프로젝트 오일러 웹서핑을 하다가 1번 문제부터 등차수열의 합과 차로 O(1)의 복잡도를 가진 코드를 짠 사람을 보고 크게 뭔가 얻어맞은 느낌이었다.

그리고 프로젝트 오일러 문제를 풀다 보니 점점 수학적으로 풀어야 한다는 생각이 들게 됐고
어느 순간 부터 그렇게 문제를 접근해 나갔는데 다시 1번 문제를 보니까 이게 그냥 for loop 1000번 돌려서 해결해야 하는 문제가 아니라는 걸 알게 된 것이다.

1000 미만이니까 999까지의 숫자로 계산하면 될 것이다.
3의 배수의 합, 그리고 5의 배수의 합을 구한뒤에 더하면 될 건데
여기에 3의 배수이면서 5의 배수인 15의 배수의 합을 빼줘야 한다. 그러면 원하는 답을 얻을 수 있게 된다.

우선 3의 배수라 하면 등차수열로 표현해 보자면 다음과 같다.

3, 6, 9, 12, ...

첫째항(a): 3
마지막항(l): 999
갯수(n): 333
공차(d): 3

갯수(n)의 경우는 999를 3으로 나눈 몫으로 구할 수 있다.

5의 배수 역시 등차수열로 표현해 보자면 다음과 같다.

5, 10, 15, 20, ...

첫째항(a): 5
마지막항(l): 995
갯수(n): 199
공차(d): 5

15의 배수 역시 등차수열로 표현해 보자면 다음과 같다.

15, 30, 45, 60, ...

첫째항(a): 15
마지막항(l): 990
갯수(n): 66
공차(d): 15

그러면 두 가지의 공식 중 하나를 사용해도 합을 구할 수 있게 된다.

Sn = n * (a + l) / 2
Sn = n * (2a + (n - 1) * d) / 2

이 공식에 대한 내용은 brilliant.org에서 자세히 확인 가능하다.

첫번째는 공차만 모를 경우 쓰는 식이고
두번째는 마지막항을 모를 경우 쓰는 식이다. 아무거나 적용해도 같은 결과를 얻을 수 있다.

등차수열의 합을 적용할 수 있는 함수를 하나 만들고
각각 3의 배수, 5의 배수, 15의 배수의 합을 구한 뒤 계산한다.

public static int SumOfAP(int n, int a, int l) {
    return n * (a + l) / 2;
}

이 문제를 다시 풀게 된 계기는 설명했으니 소감을 말해보자면 어렸을 적 소중하고 아름답게 간직하고 즐겨왔던 어떤 자연의 법칙과 비밀을 잘 알고 다루고 있었는데, 어느 순간 어른이 되고 사회에 물들면서 잠시 잊고 있었다가 다시 그 자연의 법칙을 다시 알게되서 너무 신나고 잊었던 걸 다시 찾아서 너무 기쁜 감정이 솟아오르는 느낌이다.