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

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

1003번: 피보나치 함수

---

 

틀린 Code 

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

public class Main {
	
	static int count0 = 0;
	static int count1 = 0;
	
	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 t = Integer.parseInt(br.readLine());
		
		for(int i=0;i<t;i++) {
			int n = Integer.parseInt(br.readLine());
			
			count0 = 0;
			count1 = 0;
			
			fibonacci(n);
			
			bw.write(count0+" "+count1+"\n");
		}
		
		br.close();
		bw.close();
	}
	
	public static int fibonacci(int n) {
	    if (n == 0) {
	    	count0++;
	    	return 0;
	    } else if (n == 1) {
	    	count1++;
	    	return 1;
	    } else {
	        return fibonacci(n-1) + fibonacci(n-2);
	    }
	}
}

---

처음 문제를 보고 재귀함수로 풀었는데 시간초과가 나왔다.

다이나믹 프로그래밍으로 풀어야되는 문제다.

 

다이나믹 프로그래밍은 계산을 한번 씩만 하도록하는 것이고 중복해서 계산을 해야될 순간에 이미 저장된 계산값을 불러와 이미 했던 계산을 또 하지 않아도 되어 시간단축을 할 수 있다.

 

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

public class Main {

	static int[][] arr = new int[2][41];
	
	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 t = Integer.parseInt(br.readLine());
		arr[0][0] = 1;
		arr[1][1] = 1;
		
		for (int i = 0; i < t; i++) {
			int n = Integer.parseInt(br.readLine());
			
			int[][] ptr = fibonacci(n,arr);
			
			bw.write(ptr[0][n]+" "+ptr[1][n]+"\n");
		}

		br.close();
		bw.close();
	}

	public static int[][] fibonacci(int n,int[][] arr) {
		for(int i=2;i<=n;i++) { // 2부터 n까지 0 과 1이 호출된 횟수를 저장한다.
			arr[0][i] = arr[0][i-1] + arr[0][i-2];
			arr[1][i] = arr[1][i-1] + arr[1][i-2];
		}
		return arr;
	}
}

---

2차원 배열을 만들어 arr[0]에는 index마다 0이 호출된 횟수를 저장하고,  arr[1]에는 index마다 1이 호출된 횟수를 저장했다.

 

문제를 풀 때 계속 피보나치 수열의 값을 저장하고 호출된 횟수를 저장하려고 했었는데 피보나치 수열의 값은 전혀 필요가 없었다. 

이렇게 생각하기까지 시간이 좀 걸렸다.