피보나치 함수

Day 7: 1003

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

문제 내의 함수를 이용해서, base case때 값을 return하지 말고

선언해 놓은 전역 변수를 increment 한다

바빠서 아는 개념 문제 하나 가져와서 풀었다

예시 함수도 문제가 알려주고 있고

기본적인 recursion을 사용하는 문제다

오늘은 기쁘게 공부하지 못하고 의무적으로 풀었다는 느낌이 들어 개인적으로 부끄럽다

대신에 내일 문제를 다시 풀어보고

실행시간을 500MS 이내로 줄여봐야겠다

----------------------------------------------

Thu Dec 7th, 2017 3:58AM

DP를 이용해 점화식을 세워 풀면 시간이 획기적으로 줄어든다는데

이해부터 하고 풀어봐야겠다

---

Sat Feb 10th, 2018 9:53PM

무려 2달만에 Revisit했다... DP고 뭐고 쓸 일 없고, Memoization은 굳이 쓰자면 아주 조오금 최적화 되는 정도? 그냥 간단하게 생각해서 패턴만 찾아내면 실행시간이 더 빨라진다. 피보나치 수열의 기본 규칙처럼, fib(N)을 call했을 때 fib(0)과 fib(1)이 call되는 total 빈도도 비슷한 규칙을 가진다.

ex) 

N	# of times fib(0) called	# of times fib(1) called
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3

fib[i][j]에 fib(0)과 fib(1)의 정보가 담긴다고 할 때,

fib[N][0] == fib[N-1][1] 이고,

fib[N][1] == fib[N-1][0] + fib[N-1][1] 이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class b1003_3
{
    static int[][] fib = new int[41][2];
 
    static int[] calcFibo(int N)
    {        
        if (fib[N][0] != -1) return fib[N];
        for (int i = 2; i <= N; i++)
        {
            for (int j = 0; j < 2; j++)
            {
                if (j == 0) fib[i][j] = fib[i-1][1];
                else fib[i][j] = fib[i-1][0] + fib[i-1][1];
            }
        }
        return fib[N];
    }
 
    public static void main(String[] args) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sbl = new StringBuilder();
        for (int i = 0; i < 41; i++)
        {
            for (int j = 0; j < 2; j++)
            {
                fib[i][j] = -1;
            }
        }
        fib[0][0] = 1; fib[0][1] = 0;
        fib[1][0] = 0; fib[1][1] = 1;
 
        for (int i = 0; i < T; i++)
        {
            int N = Integer.parseInt(br.readLine());
            int[] res = calcFibo(N);
            
            for (int j: res)
            {
                sbl.append(j).append(" ");
            }
            sbl.append("\n");
        }
        System.out.println(sbl.toString());
    }
}

---