[백준 알고리즘] 1003 피보나치 함수 (21.05.16)

오늘은 

 

바로

 

바로

 

.

.

.

 

다이나믹 프로그래밍 !!!!!!!!!!!! 

 

입니다

 

 

 

 

 

---

 

 

그래서 오늘의 문제는

 

 

백준 1003번 피보나치 함수

 

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

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

 

출력

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

 

 

문제 사이트 : https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

 

 

 

---

여기서 핵심 포인트!!!

 

 

- 시간초과를 어떻게 막을 것인가!!!!!

 

 

-피보나치수열에서 어떤 또 다른 규칙을 찾아내는가!!

 

---

 

 

 

 

 

 

직접 작성해본 소스코드 및 간단한 설명

 

 

• 첫 번째 코드!!

라 하고 시간 초과된 코드라고 한다 ㅎ,,,

import java.util.Scanner;

public class Main {

	static int [] zero;
	static int [] one;
	
	static int fibonnacci(int n, int i) {
		if(n==0) {
			zero[i]++;
			return 0;
		}else if(n ==1) {
			one[i]++;
			return 1;
		}else {
			return fibonnacci(n-1, i) + fibonnacci(n-2, i);
		}
	}
	
	static void initArray(int size) {
		for(int i = 0; i < size; i++) {
			zero[i] = 0;
			one[i] = 0;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		zero = new int[T];
		one = new int[T];
		initArray(T);
		
		for(int i = 0; i< T; i++) {
			int tmp = sc.nextInt();
			fibonnacci(tmp, i);
		}
		
		for(int i = 0; i< T; i++) {
			System.out.println(zero[i] + " " + one[i]);
		}
		
	}
}

 

간단히 설명하자면 . . .

 

 

• 피보나치 함수를 이용한 코드

 

 

.

.

.

 

라고 밖에 설명을 못하는 아주 간단한 코드이다 !!

 

 

 

 

당연스럽게도 시간초과가 걸렸고

 

백준 1003번 시간초과

 

 

어떻게 해결하면 좋을지 고민한 결과

 

.

.

.

 

 

 

---

 

 

• 두 번째 코드 !!!!

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

public class Main {

	static int [] zero;
	static int [] one;
	
	static int fibonnacci(int n, int i) {
		if(n==0) {
			zero[i]++;
			return 0;
		}else if(n ==1) {
			one[i]++;
			return 1;
		}else {
			return fibonnacci(n-1, i) + fibonnacci(n-2, i);
		}
	}
	
	static void initArray(int size) {
		for(int i = 0; i < size; i++) {
			zero[i] = 0;
			one[i] = 0;
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = Integer.parseInt(br.readLine());
		zero = new int[T];
		one = new int[T];
		initArray(T);
		
		for(int i = 0; i< T; i++) {
			int tmp = Integer.parseInt(br.readLine());
			fibonnacci(tmp, i);
		}
		
		for(int i = 0; i< T; i++) {
			bw.write(zero[i] + " " + one[i] + "\n");
		}
		
		br.close();
		bw.close();
	}
}

 

여기서 중요한 점은 !!!

 

 

• Scanner와 System.out.print() 가 시간이 오래 걸린다는 점 !!!

 

• BufferedReader와 BufferedWriter로 대체!!!

 

 

 

 

 

 

그럼에도 불구하고

 

 

시. 간. 초. 과.

 

백준 1003 두 번째 시간 초과

 

 

 

 

결국 피보나치수열 함수를 사용하는 것을 포기하기로 했다 !!! 

 

 

 

 

 

---

 

 

 

그렇게 선택한 코드는 

 

• 세 번째 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = Integer.parseInt(br.readLine());
		int [] zero = new int[41];
		int [] one = new int[41];
		
		zero[0] = 1;
		zero[1] = 0;
		one[0] = 0;
		one[1] = 1;
		
		for(int i = 0; i< T; i++) {
			int tmp = Integer.parseInt(br.readLine());
			for(int j = 2; j <= tmp; j++) {
				zero[j] = zero[j-1] + zero[j-2];
				one[j] = one[j-1] + one[j-2];
			}
			bw.write(zero[tmp] + " " + one[tmp] + "\n");
		}
		br.close();
		bw.close();
	}
}

 

간단하게 설명하자면 ...

 

• zero와 one의 규칙 찾기!!!

 

---

 

피보나치수열을 계산해보면 쉽게 찾을 수 있다!!

 

f(0)의 개수와 f(1)의 개수를 순서대로 따져보면

 

f(0)	1	0
f(1)	0	1
f(2)	1	1
f(3)	1	2
f(4)	2	3

 

즉   i 가 1보다 클 때,

 

zero[i] = zero[i-1] + zero[i-2]

one[i] = one[i-1] + one[i-2]

 

라는 결론을 얻을 수 있다!!

 

 

---

 

 

 

 

 

백준 알고리즘

 

채점 결과!!!

 

 

 

다행히 맞았습니다!!

백준 1003번 채점 결과

 

 

 

 

 

 

 

---

스터디하면서 나온 더 좋은 방법들

• 배열 [][]로 사용하여 한 번에 받기!
• 먼저 40개의 zero, one 배열을 계산해두어 중복 계산 제거!!

 

 

스터디하면서 생긴 의문

• 먼저 40개의 zero, one 배열을 계산해주기 vs. 입력받을 때마다 check 해주기
• 둘 다 시간은 동일하게 나오는데 왜 그런 것일까?