[백준] 1003번 : 피보나치 함수

1003번: 피보나치 함수

# 입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

# 출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

# 예제 입력

3
0
1
3

# 예제 출력

1 0
0 1
1 2

문제를 보면 우리가 흔히 알고있는 피보나치 수열 문제처럼 재귀적인 방법으로 풀 수 있다. 하지만 정답의 조건 때문에 이 문제는 동적 프로그래밍(Dynamic Programming)으로 해결해야 한다. 바로 "시간" 때문이다.

0<= N <= 40 이므로 40이 3회 주어졌다고 가정해보면, 0.25s 만에 프로그래밍을 마치는 것은 어렵다고 생각된다. 따라서 반복적인 호출이 많은 부분이므로 동적 프로그래밍을 이용하여 문제를 풀어보자.

 

피보나치 수열 함수를 f()라고 하자. n >= 2일 때 f(n-1) + f(n-2) 이다. 지금은 f(n)의 값을 찾는 것이 아닌 f(n)에서 f(0)과 f(1)을 몇 번 호출하느냐가 문제이므로,

 

f(0) = [1, 0]

f(1) = [0, 1]

f(2) = f(0) + f(1) = [1, 1]

f(3) = f(2) + f(1) = (f(0) + f(1)) + f(1) = [1, 2]

...

 

따라서 f(n)의 f(0), f(1) 호출 횟수는 f(n) = f(n-1)의 f(0), f(1) 호출 횟수 + f(n-2)의 f(0), f(1) 호출 횟수와 같다.

먼저, 2차원 배열 long arr[41][2]가 필요하다. (arr[i][0] : 0의 개수, arr[i][1] : 1의 개수)

static void fibo(int n){

  arr[0][0] = 1; arr[0][1] = 0;
  arr[1][0] = 0; arr[1][1] = 1;

  for (int i = 2; i <= n; i++) {
    arr[i][0] = arr[i - 1][0] + arr[i - 2][0];
    arr[i][1] = arr[i - 1][1] + arr[i - 2][1];
  }
}

만약 이 함수가 1번만 실행이 된다면 상관없지만, 5번 실행된다면?

n = [10, 7, 5, 3, 13] 순으로,

10이 들어오고 arr[10][0] arr[10][1] 까지는 값이 채워져 있다.

7이 들어왔을 때 arr[7][0] arr[7][1] 은 이미 값이 채워져 있는대도 for루프가 실행이 된다.

 

전역 변수로 max를 만들어서 인자로 들어오는 n과 max를 비교해서 n < max라면 for루프를 실행시키지 않도록 하자.

 

    static int max = 2;
    static long[][] arr = new long[41][2];

    static void fibo(int n){
        arr[0][0] = 1; arr[0][1] = 0;
        arr[1][0] = 0; arr[1][1] = 1;

        if(n > max) {
            for (int i = max; i <= n; i++) {
                arr[i][0] = arr[i - 1][0] + arr[i - 2][0];
                arr[i][1] = arr[i - 1][1] + arr[i - 2][1];
            }
            max = n;
        }
        System.out.printf("%d %d\n", arr[n][0], arr[n][1]);
    }

 

이제 main()에서는 T와 N값들을 입력받아 함수 인자로 넘겨주기만 하면 끝이다.

---

# Java Code </>

public class Main {

    static int max = 2;
    static long[][] arr = new long[41][2];

    static void fibo(int n){
        arr[0][0] = 1; arr[0][1] = 0;
        arr[1][0] = 0; arr[1][1] = 1;

        if(n > max) {
            for (int i = max; i <= n; i++) {
                arr[i][0] = arr[i - 1][0] + arr[i - 2][0];
                arr[i][1] = arr[i - 1][1] + arr[i - 2][1];
            }
            max = n;
        }
        System.out.printf("%d %d\n", arr[n][0], arr[n][1]);
    }
    
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();

        long start = System.currentTimeMillis();
        for(int i=0; i<T; i++)
            fibo(sc.nextInt());

        long end = System.currentTimeMillis();
        System.out.println( "실행 시간 : " + ( end - start )/1000.0 +"초");
    }
}

그런데 시간제한이 0.25초라... Java의 Scanner를 사용하면 시간 초과가 발생한다 ㅠㅠ.. 참고로 백준에서 제출 시 Java를 이용한다면.. java - java(openJDK) - java 11 순으로 빠르다고 한다. 계속 시간 초과가 나니까 짜증나서 그냥 C로 제출해버렸다.

 

# C Code </>

#include <stdio.h>

int max = 2;
long arr[41][2];

void fibo(int n) {

	arr[0][0] = 1; arr[0][1] = 0;
	arr[1][0] = 0; arr[1][1] = 1;

	if (n >= max) {
		for (int i = max; i <= n; i++) {
			arr[i][0] = arr[i - 1][0] + arr[i - 2][0];
			arr[i][1] = arr[i - 1][1] + arr[i - 2][1];
		}
		max = n;
	}
	printf("%d %d\n", arr[n][0], arr[n][1]);
}

int main(void) {

	int T, n;
	scanf("%d", &T);

	for (int i = 0; i < T; i++) {
		scanf("%d", &n);
		fibo(n);
	}
}