백준 1003번: 피보나치 함수

//성공
public void calculate(int val[]) {
		
		for (int i : val) {

			int oneBefore = 0;
			int oneAfter = oneBefore;
			int zero = 1;

			if (i > 0) {
				oneBefore = 1;
				oneAfter = oneBefore;
				zero = 0;
				for (int j = 1; j < i; j++) {
					oneAfter = oneBefore + zero;
					zero = oneBefore;
					oneBefore = oneAfter;
				}
			}

			System.out.println(zero + " " + oneAfter);
		}
	}

//실패 - 시간초과
static int fibonacci(int n) {
		int val = 0;
		
		if(n > 1) {
			val = fibonacci(n - 1) + fibonacci(n - 2);
		}else {
			val = n;
		}

		return val;
	}

 

 

0.25초 라는 시간제한에서 많이 애 먹었다.

테스트 삼아 0~9 까지의 값을 입력하여 도출 해보면.

 

i>1 일때 fibonacci , zero (0), one (1) 을 계산 하였을 때

 

zero 는 이 전 fibonacci 의 one 갯수.

one 은 이 전 finonacci 의 zero + one 갯수 를 충족 시킨다.

 

점화식은 dp[n-1] + dp[n-2] (fibonacci) = dp[n-1] (zero) , dp[n] (one) 으로 도출하였지만, 

막상 로직은 점화식 자체를 생각하지 않아도 해결 될만한 문제같다.