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

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

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

정확히 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; } }