백준 1003. 피보나치 함수

문제 링크

난이도	정답률(_%)
Silver 3	29.462%

설계

• 계산해야할 자연수 N <= 40
• 피보나치 수열과 마찬가지로, 호출된 횟수도 n = (n-1) + (n-2) 형태이다. 따라서 배열에 각 수가 호출된 횟수를 넣어주면서 n까지 계산한다.

시간 복잡도

• O(N)

공간 복잡도

• 호출 횟수를 저장할 int형 배열 길이 41

풀이

• 길이 41의 배열에 초기 값인 0, 1을 호출했을 때의 호출 횟수를 저장한다.
• 2부터 N까지 n = (n-1) + (n-2) 형태로 배열에 값을 저장해 return 한다.

결과

메모리	실행 시간
12988KB	72ms

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int testCase = Integer.parseInt(br.readLine());

        for (int i = 0; i < testCase; i++) {
            int number = Integer.parseInt(br.readLine());
            CallNumber callNumberOfN = getCallNumber(number);

            bw.write(callNumberOfN.toString());
        }

        bw.flush();
        bw.close();
    }

    public static CallNumber getCallNumber(int n) {
        CallNumber[] zeroNOne = new CallNumber[41];

        zeroNOne[0] = new CallNumber(1, 0);
        zeroNOne[1] = new CallNumber(0, 1);

        for (int i = 2; i <= n; i++) {
            int zero = zeroNOne[i - 1].zero + zeroNOne[i - 2].zero;
            int one = zeroNOne[i - 1].one + zeroNOne[i - 2].one;

            zeroNOne[i] = new CallNumber(zero, one);
        }

        return zeroNOne[n];
    }
}

class CallNumber {
    int zero;
    int one;

    public CallNumber(int zero, int one) {
        this.zero = zero;
        this.one = one;
    }

    public String toString() {
        StringBuffer sb = new StringBuffer();

        sb.append(String.valueOf(zero));
        sb.append(" ");
        sb.append(String.valueOf(one));
        sb.append("\n");

        return sb.toString();
    }
}