Q1003

처음 백준 알고리즘을 접했을때 1000부터 정복한다 ㅋㅋㅋ

하는마음으로 1000번부터 덤볐던 기억이난다.

터렛에서 무슨소린지 못알아듣고 처음에 피보나치라는 개념은 학부시절에 들어서 재귀이고 이렇게 짠다는것 정도 밖에 몰랐다.

그때 코드이다.

import java.util.*;
 
public class Main{
    public static int zero = 0;
    public static int one = 0;
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        
        int testCaseNum = Integer.parseInt(sc.nextLine());
        
        for(int i = 0; i < testCaseNum; i++) {
            fibonacci(sc.nextInt());
            sc.nextLine();
            System.out.println(zero + " " + one);
            zero = 0; 
            one = 0;
        }
    }
    public static int fibonacci(int n) {
        if (n == 0) {
            zero++;
            return 0;
        } else if (n == 1) {
            one++;
            return 1;
        } else {
            return fibonacci(n-1) + fibonacci(n-2);
        }
    } 
}
 

0.25초라는 시간제한도 있는 문제이고. 

40번이뭐냐 20번만 넣어도 터지는 코드이다.

당연 실패했고 한번 실패한 뒤에 이것저것 찾아보기 시작했다.

몇주 지난뒤에 이것저것 풀다보니 동적 프로그래밍 메모이제이션에 대한 개념을 접하고 

bottom -> top으로 가는 방향이 편하게 구현할 것 같아서 40이라는 제한이 주어져 있으니 미리 구해서 테스트케이스 숫자만 반환하는 형식으로 교체했다.

import java.util.Scanner;
 
public class Main {
 
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
 
        int testCaseNum = Integer.parseInt(sc.nextLine());
        
        
        int[][] fiboArray = new int[41][2];
        fiboArray[0] = new int[]{1, 0};
        fiboArray[1] = new int[]{0, 1};
        for(int i = 2; i < fiboArray.length; i++) {
            fiboArray[i] = new int[] {fiboArray[i-2][0] + fiboArray[i-1][0], fiboArray[i-2][1] + fiboArray[i-1][1]};
        }
        
        int testNum = 0;
        for (int i = 0; i < testCaseNum; i++) {
            testNum = Integer.parseInt(sc.nextLine());
            System.out.println(fiboArray[testNum][0] + " " + fiboArray[testNum][1]);
        }
        sc.close();
    }
 
 
}