알고리즘 풀이/백준

[백준][Java] 1003번 피보나치 함수

배게 2018. 4. 30. 04:47
728x90

재귀함수로 하면 시간초과납니다..


피보나치수열이 가진 규칙을 이용하여

정확히 n번째 필요한 0의 개수를 활용하여

1의 개수까지 함께 출력합니다.

규칙을 찾는 것이 무엇보다 중요합니다.


 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
31
32
33
34
35
36
37
import java.util.*;

public class Main {
	
	
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		int[] res_prt = new int[2];
		
		for(int i=0; i<T; i++) {
			int n=sc.nextInt();
			System.out.println(fibo(n)+" "+fibo(n+1));
			
		}
	}
	
	private static int fibo(int n) {
		if(n==0) return 1;
		if(n==1) return 0;
		
		int a=1;
		int b=0;
		int c=1;
		
		for(int i=0; i<n-2; i++) {
			a=b;
			b=c;
			c=a+b;
		}
		
		return c;
		
	}
}