Script / CSS

G1sUtil.js

G1sBlogger.js

G1sNavigationList.js

G1sCode

Posts List

2012년 2월 11일 토요일

[Project Euler] 1. 1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면?

1. 1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면?

10보다 작은 자연수 중에서 3 또는 5의 배수는 3, 5, 6, 9 이고, 이것을 모두 더하면 23입니다.
1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면 얼마일까요?
Click

첫문제는 역시 간단하게....

놀라운건 이 문제를 풀고 들어갔더니 대부분의 분들이 1~1000까지 for문을 돌며 3의 배수 또는 5의 배수이면 sum값에 더해주면서 푸는 방식을 택했다는 것.

그런 방식은 가장 단순하고 확실하겠지만.... 효율면에서 좋은거라고 보기 힘들죠.
그것 보다는 이같은 경우 등차수열의 합을 구하는 공식을 적용하면 쉽게 결과가 나오는 문제.

위키백과 : 등차수열

결론적으로 등차수열의 합의 원리는 {an}의 중앙값 x {an}의 항의 개수로 정리 할 수 있다.(단, {an}은 유한수열)

그리고 여기서 고려할게 3과 5 두 수의 최소공배수인 15의 합또한 빼줘야 한다는 것.

위에 등차수열의 합 공식을 ∑을 이용해 나타내고, 최대치 max/a(a=3,5,15) 의 값을 각각 n₁,n₂,n₃로 놓으면, 결국 공식은...

result = 3∑n₁+ 5∑n₂- 15∑n₃

이렇게 풀기는 너무 간단하니까 이 함수를 일반화를 하여, a,b값과 max값을 입력받으면 그에 해당하는 배수의 합을 구하는 함수를 만들면
<script>
/** 유클리드 알고리즘을 통해 최대 공약수와 최소 공배수를 구함. **/
function euclid(a,b){
 if (b == 0) return a;
 return euclid(b, a % b);
}

/* 최대 공약수 */
function gcd(a,b){
 return euclid(Math.max(a,b),Math.min(a,b));
}

/* 최소 공배수 */
function lcm(a,b){
 return (a*b) / gcd(a, b);
}

/** 등차 수열의 합. **/
function sigma_ak(n1, n2, a){
 return parseInt((n2-n1 + 1) * ((n2+n1) / 2.0) * a);
}

/** max 보다 작은 n의 배수들의 합. **/
function sumMultiples(n, max){
 var cnt = parseInt(max / n);
 return sigma_ak(0, cnt, n);
}

/** max 보다 작은 n1,n2의 배수들의 합. **/
function sum2Multiples(n1, n2, max){
 var sum1 = sumMultiples(n1, max);
 var sum2 = sumMultiples(n2, max);
 var sumLcn = sumMultiples(lcm(n1,n2), max);
 
 return sum1 + sum2 - sumLcn;
}
</script>
코드가 좀 긴가요?
함수로 쪼개넣고 깔끔하게 보이기 위해 그런 듯 보이지만 합쳐놓고 보면 그렇게 길지도 않죠.

효율은 0부터 max까지 a,b의 배수를 더하는 것과는 비교도 되지 않는

최대 공약수를 구하는 법은 유클리드 안고리즘을 이용했습니다.

댓글 없음:

댓글 쓰기