http://codingdojang.com/scode/350
이 문제를 보고 풀이를 생각했습니다.
c/c++/c#기준입니다.
처음에는 다른 사람들 처럼 다음과 같은 풀이를 생각했습니다.
int sum = 0;
for (int i = 1; i < 1001; i++)
{
if (i % 3 == 0 || i % 5 == 0)
sum += i;
}
1~1000까지 반복문으로 전부 돌면서 3이나 5의 배수이면 결과값에 더해주는거죠.
그런데 이게 무조건 확정적으로 1000번을 돈다는게 마음에 안 들더라구요.
그래서 다음엔 코드는 좀 길어지지만 for문을 덜 돌게 수정을 해봤습니다.
int sum = 0;
for (int i = 3; i < 1001; i += 3)
{
sum += i;
}
for (int i = 5; i < 1001; i += 5)
{
sum += i;
}
for (int i = 15; i < 1001; i += 15)
{
sum -= i;
}
이번에는 3의 배수와 5의 배수를 주륵 더하고, 3과 5의 공배수(15의 배수)는 겹쳐서 두번 들어갈테니 한번 빼줬습니다.
그러면 333 + 200 + 66 = 599번만 반복문을 돌게됩니다.
길이와 가독성을 희생했지만 반복량은 절반도 줄이지 못 했습니다.
이에 아예 반복문을 안 돌수는 없을까? 라는 생각을 가지고 다음과 같은 방식을 떠올렸습니다.
일단 3의 배수 총합은. 배수들의 총 갯수(3,6,9면 3개) 곱하기 3. 이죠.
즉 3+6+9 = 3 * (1+2+3)
마찬가지로 5의 배수 총합은
5 + 10 + 15 = 5 * (1 + 2 + 3)
그리고 자연수의 총합은 중학생인가 고등학생때 배우던가요?
예를 들어 1~n까지 더하는거면. (1 + n) * n / 2
즉 1~1000 중에서 3의 배수의 총합을 구하는 식은
1~1000까지 3의 배수 갯수는 1000 / 3 (나머지 버림) = 333개.
3 * (1 + 333) * 333 / 2
이런 공식을 하나의 함수로 정의하자면.
//multiple = 배수. maxNum = 최대 수(이 문제의 경우 1000)
int GetMultipleSum(int multiple, int maxNum)
{
int count = maxNum / multiple;
return multiple * ((1 + count) * count / 2);
}
그리고 3과 5의 배수의 총합은 두번째 풀이때 언급했듯이.
3의 배수 총합 + 5의 배수 총합 - 15의 배수 총합
int sum = GetMultipleSum(3, 1000) + GetMultipleSum(5, 1000) - GetMultipleSum(15, 1000);
이렇게 하면 반복문 없이 바로 답이 나오네요.
이 보다도 더 좋은 방법이 있을 것 같긴한데. 아이디어가 안 떠오르네요.
