백준 알고리즘 1003번 풀이 - 피보나치 함수

 

피보나치 함수에서 0과 1이 몇 번 출력되는지 구하는 문제입니다.

저기서 printf대신 zero와 one을 1씩 더해줘서 풀게되면 시간초과가 뜨게 됩니다.

 

7까지의 0과 1을 계산해 보면 아래와 같은 결과가 나옵니다.

1의 갯수를 보면 피보나치 수열로 증가하고 0은 n-1의 1의 갯수와 같습니다.

시간을 줄이기 위하여 n의 1의 갯수만 구하고 0의 갯수는 n-1번째 값을 입력해 주면 됩니다.

 

import java.util.Scanner;

public class Main {
	static int[] result = new int[41];
	
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		
		int T = s.nextInt();
		result[0]=0;
		result[1]=1;
		for(int j=2;j<41;j++){
			result[j]=result[j-1]+result[j-2];
		}
		for(int i=0;i<T;i++){
			int n = s.nextInt();
			if (n==0)System.out.println("1 0");
			else System.out.println(result[n-1]+" "+result[n]);
		}
	}
}

n이 40까지로 얼마 되지 않아 미리 for문을 통해 계산을 하고 밑에서는 출력만 해주엇습니다.

0일 경우는 에러가 나기 때문에 하드코딩해 줬습니다....