[알고리즘] 백준 1003번 : 피보나치 함수

 

문제

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

 

📌 내 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
	
	static Integer[][] count;
	
    public static void main(String[] args) throws IOException  {
    	
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	// 테스트 케이스 수
    	int T = Integer.parseInt(br.readLine());
    	
    	for(int i=0; i<T; i++) {
    		StringBuilder sb = new StringBuilder();
    		
    		// 피보나치 수
    		int N = Integer.parseInt(br.readLine());
    		
    		// 1 과 0이 몇 번째 호출됐는지 세는 배열
    		count = new Integer[N+1][2];
    		
    		for(int k=0; k<=N; k++ ) {
    			if(k==0) {  // 피보나치 수가 0일 때 
    		   		count[k][0] = 1;  // 0은 1번 출력
    	    		count[k][1] = 0;  // 1은 0번 출력
    	    		continue;
    			}
    			
    			if(k==1) {  // 피보나치 수가 1일 때
    	    		count[k][0] = 0;  // 0은 0번 출력
    	    		count[k][1] = 1;  // 1은 1번 출력
    	    		continue;
    			}
    			
    			// 피보나치 수가 아직 구해지지 않았을 때
    			if(count[k][0] == null || count[k][-1] == null) {
    				
    				// k의 0번쨰 호출 = (k-1) 0번쨰 호출 수 + (k-2)의 0번쨰 호출 수 
    				count[k][0] = (count[k-1][0] + count[k-2][0]);
    				// k의 1번쨰 호출 = (k-1) 1번쨰 호출 수 + (k-2)의 1번쨰 호출 수 
    				count[k][1] = (count[k-1][1] + count[k-2][1]);
    			}
    		}

    		sb.append(count[N][0])
    			.append(" ")
    			.append(count[N][1]);
    		System.out.println(sb);
    	}
    }
}

 

📌 참고할 만한 풀이 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
	
	static Integer[][] count = new Integer[41][2];
	
    public static void main(String[] args) throws IOException  {
    	
    	count[0][0] =1;
    	count[0][1] = 0;
    	count[1][0] = 0;
    	count[1][1] = 1;
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	int T = Integer.parseInt(br.readLine());
    	
    	while(T --> 0) {
    		int N = Integer.parseInt(br.readLine());
    		StringBuilder sb = new StringBuilder();
    		
    		fibo(N);
    		
    		sb.append(count[N][0])
    			.append(" ")
    			.append(count[N][1]);
    		System.out.println(sb);
    		
    	}
    }
    
    static Integer[] fibo(int n) {
    	if(count[n][0]==null || count[n][1]==null) {
    		count[n][0] = fibo(n-1)[0] + fibo(n-2)[0]; 
    		count[n][1] = fibo(n-1)[1] + fibo(n-2)[1]; 
    	}

    	// count[n][0], count[n][1]을 담고 있는 count[n]을 반환한다.
    	return count[n];
    }
}

 

 

 

---

👀 참고자료

https://st-lab.tistory.com/124