문제 원본

https://www.hackerrank.com/contests/projecteuler/challenges/euler002


문제 요약

N 미만의 피보나치 수열 중 2의 배수를 모두 합한 값. (단, 최초 2개의 숫자는 1, 2로 시작함)



-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
29
30
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
 
public class Solution {
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for(int a0 = 0; a0 < t; a0++){
            long n = in.nextLong();
            
            long sum = 0;
            long prev = 1, fibo = 2, tmp = 0;
            
            while(fibo < n){
                if(fibo%2 == 0)
                    sum += fibo;
                
                tmp = prev;
                prev = fibo;
                fibo += tmp;
            }
            
            System.out.println(sum);
        }
    }
}
cs



- 주의할 점!

  같은 연산을 반복 수행한다고 해서 재귀함수로 구현하면 쓰뜌삣!!!!!!!!!!!! 그러면 공간복잡도 꽝꽝꽝



천천히, 꾸준히 syaring's study

저작자표시 비영리 변경금지 (새창열림)

'syaring_Study > algo_Project Euler' 카테고리의 다른 글

| 20171208 | Project Euler #1: Multiples of 3 and 5 | HackerRank  (0) 2017.12.08

문제 원본

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

+ Recent posts

티스토리툴바