[백준 2024/01/22] 1003번 피보나치 함수

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

1. 접근 방법

이번 문제의 눈에 띄는 특징은 단연 시간과 메모리 제한이라고 할 수 있다.

시간 제한의 경우 0.25초, 메모리 제한의 경우 128MB 이었다.

 

즉, 재귀 함수가 대놓고 문제에 적혀져 있지만 그것은..! 함정이다!

정답 비율이 낮은 이유가 여기에 있을 것 같다.

코드가 적혀져 있다고 해당 코드를 이용하여 문제를 풀면 시간 초과로 풀지 못한다.

 

또한, 시간 제한이 이렇게 낮다? -> 규칙이 있을 것 같다.

라는 느낌이 들었다. 그래서 피보나치 수들을 하나씩 적어나갔고, 규칙을 찾아낼 수 있었다.

 

rough draft

 

0의 개수의 경우 이전 피보나치의 1의 개수와 같다는 점이다.

즉 , f(n-1) -> 0의 개수

f(n) -> 1의 개수

가 될 것이다.

 

또한 피보나치 수열의 경우 재귀가 아니도록 식을 작성해주었다.

+ f(n)에서 n이 0 인 경우엔 따로 처리해주었다.

 

2. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Deque;
import java.util.ArrayDeque;
import java.util.List;


public class b1003 {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int num = Integer.parseInt(reader.readLine());

        for(int i = 0; i<num; i++) {
            int f = Integer.parseInt(reader.readLine());

            fibonacci(f);

        }
    }
    public static void fibonacci(int n){
        int now = 0;
        int before = 0;
        int count = 0;
        int temp = 0;
        while(count!=n) {
            if (now == 0) {
                now += 1;
                count += 1;
            } else {
                temp = before;
                before = now;
                now = now + temp;
                count += 1;
            }
        }
        if(before==0 && now == 0){
            System.out.println("1 0");
        }
        else{
            System.out.println(before + " " + now);
        }
    }

}