백준 알고리즘 1003번 피보나치 함수 0과 1 개수 카운팅 JAVA

 

 

 

백준 알고리즘 1003번은 기존 피보나치 수를 구하는 알고리즘에서 나아가 0과 1의 수를 세는 문제다. fibonacci() 메소드를 실행하면 최종적으로 매개변수값이 1까지 줄어들게 되면서 마지막에는 0과 1이 카운팅 되기 때문에  주어진 자연수(40보다 작거나 같은 수)에 따라서 0와 1의 개수가 달라진다.

 

먼저 for문을 순회하면서 입력값을 받아오고, 다시 for문을 순회하면서 fibonacci() 메소드를 순차적으로 실행시키는 코드를 작성했다. 결과값은 맞게 나오지만 백준 코딩 사이트에서는 시간초과가 걸린다. 피보나치 로직을 그대로 실행시키면서 숫자를 구해도 되지만 시간초과에는 해결이 안된다.

 

JAVA CODE #1 (시간초과 코드)

import java.util.Scanner;

public class A_1003 {
    public static int[] arr;
    public static int count_0=0;
    public static int count_1=0;

    public static void main(String [] args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();  
        arr = new int[N];
        for(int i=0; i<N; i++){
            arr[i]=in.nextInt();
        }
        
        for(int i=0; i<N; i++){
            count_0=0;
            count_1=0;
            fibonacci(arr[i]);
            System.out.println(count_0+" "+count_1);
        }

    }
    public static int fibonacci(int n){
        if(n==0){
            count_0++;
            return 0;
        }else if(n==1){
            count_1++;
            return 1;
        }else{
            return fibonacci(n-1) + fibonacci(n-2);
        }
    }
}

 

 

백준 알고리즘 1003번의 해법은 피보나치의 정의를 다시 이해하는 것이다. 문제에서 40이하의 자연수를 입력받게 된다. 피보나치는 n>=2 일 때 작동하게 된다. 입력값 0에 대해서는 0이 출력되고 1에 대해서는 1이 출력되게 된다. 이후 n-1번째 값과 n-2번째 값의 합으로 수열이 구성된다.

 

 

 

피보나치 수열의 원리를 적용한 JAVA 코드는 아래와 같다. 시간초과 없이 문제 해결완료다. 40이하의 입력된 자연수 전체 피보나치 수열을 연산한 후 테스트케이스의 value만 출력해주면 된다.

 

JAVA CODE #2 (해결코드)

import java.util.Scanner;

public class A_1003 {
    public static int[] arr;
    public static int count_0=0;
    public static int count_1=0;
    public static int[][] fiboArray=new int[42][2];

    public static void main(String [] args){

        // 입력값 받는 부분
        Scanner in = new Scanner(System.in);
        // 테스트 케이스의 수
        int N = in.nextInt();
        // 테스트 케이스 N개의 array 생성 및 value 할당  
        arr = new int[N];
        for(int i=0; i<N; i++){
            arr[i]=in.nextInt();
        }
        
        // 피보나치 입력값 초기화
        fiboArray[0][0]=1;
        fiboArray[0][1]=0;
        fiboArray[1][0]=0;
        fiboArray[1][1]=1;

        // 40 이하 자연수를 입력받았을 때 피보나치 수열 전체 연산
        for(int i=2; i<42; i++){
            fiboArray[i][0]=fiboArray[i-1][0]+fiboArray[i-2][0];
            fiboArray[i][1]=fiboArray[i-1][1]+fiboArray[i-2][1];
        }

        // 테스트 케이스의 0과 1의 값 출력
        for(int num:arr){
            System.out.println(fiboArray[num][0]+" "+fiboArray[num][1]);
        }


    }
}