문제 원본
https://www.hackerrank.com/contests/projecteuler/challenges/euler001
문제 요약
N 미만의 자연수 중, 3, 5의 배수를 모두 합한 값을 구하는 문제.
- Solution.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | import java.io.*; import java.util.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); long t = in.nextLong(); for(long a0 = 0; a0 < t; a0++){ long n = in.nextLong(); n--; long q3 = n/3; long q5 = n/5; long q15 = n/15; long sum3 = 3*(1+q3)*q3/2; long sum5 = 5*(1+q5)*q5/2; long sum15 = 15*(1+q15)*q15/2; System.out.println(sum3+sum5-sum15); } } } | cs |
- 맨 처음에 문제를 풀었을 때, 수학계산따위 안하고 무식하게 2중 for문을 썼다.. 결과는 당연히 time out...
1 2 3 4 | java머for(int i = 0; i<n; i++){ if(i%5 == 0 || i%3 == 0) sum+=i; } | cs |
- 현재 구현한 코드의 수학 계산
N 미만의 자연수 중 3의 배수의 합 (예 : N=30)
sum = 3 + 6 + 9 + 12 + .... + 27 = 135
그런데 일일이 각 숫자를 더하는 것은 굉장히 비효율적이다.
sum = 3 * (1 + 2 + 3 + ..... + 9), 9는 (30 - 1)/3의 몫
그리고 이미 알고있는 1부터 X까지의 합을 구하는 공식 (1 + M) * M/2를 (1 + 2 + 3 + ..... + 9)에 적용하면
sum = 3 * (1 + 9) * 9/2 = 135
즉, N 미만의 자연수 중 a의 배수의 합(sum)
sum = a * (1 + (N-1)/a) * (N-1)/a/2, 여기서 / 는 컴퓨터 기준, 몫
- 처음에 제공된 포맷에 Int로 되어있어서 크게 신경을 안쓰고 코딩했는데, Integer로 하니까 Wrong Answer 오류가 떴다. Integer → Long으로 수정하니 제대로 돌아간다.
천천히, 꾸준히 syaring's study
'syaring_Study > algo_Project Euler' 카테고리의 다른 글
| | 20171208 | Project Euler #2: Even Fibonacci numbers | HackerRank (0) | 2017.12.08 |
|---|