마음만은 새내기

항상 초심을 잃지 않고 생활하겠습니다~!

프로그래밍/HackerRank

Project Euler #1 (Multiples of 3 and 5) 문제 풀이

동동매니저 2019. 6. 4. 12:24
★ 문제 요약
N이 주어지면, N보다 작은 수 중에서 모든 3의 배수 또는 5의 배수의 합을 구하는 문제
예시 : N = 10일 때, 조건에 맞는 수는 3, 5, 6, 9이고, 이들의 합은 23

★ 문제 해법
단순 반복문과 조건문을 사용할 수도 있지만(O(N)), N의 범위가 최대 10억이기 때문에, 시간이 매우 오래 걸림.
하지만, 1부터 N까지의 합을 구하는 공식을 알면, 쉽게 풀 수 있음. (1부터 N까지의 합 = N(N+1)/2)
여기에서는 이 과정을 함수로 구현 (함수 이름 : S(N))
즉, S(N) = N(N+1)/2

1부터 N까지 3의 배수의 합 = S(N/3)*3
1부터 N까지 5 배수의 합 = S(N/5)*5
(단, N보다 작은 수만 계산하므로, N 대신 N-1로 계산할 것!)
이 과정을 마치면, 15의 배수가 중복으로 계산됨 (3, 5의 최소 공배수가 15이기 때문)
그러므로 우리가 구하고자 하는 정답은 S(3의 배수)+S(5의 배수)-S(15의 배수)

★ 소스 코드 (C)