[백준(Baekjoon)][자바(java)] 1003 : 피보나치 함수 / 동적 계획법 1

 

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

1003번: 피보나치 함수

 

* 문제

fibonacci(3)을 호출하면 1은 2번 출력되고, 0은 1번 출력된다.

N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는가

 

* 풀이 방법 

- fibonacci(0) 부터 차례로 0과 1이 각각 몇 번 출력되는지 카운트 해봄

- 그 결과, 0과 1의 각각의 개수가 피보나치 수열 규칙대로 늘어나는 것을 발견함

 

N	0 출력 횟수 ( f(0) 호출 횟수 )	1 출력 횟수  ( f(1) 호출 횟수 )
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3
5	3	5
6	5	8

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt(), n, a, b, c;
		while( t-- > 0 ) {
			n = sc.nextInt();
			if( n == 0 ) 
				a = 1; b = 0;
			else {
				a = 0; b = 1;
				for( int i = 2; i <= n; i++ ) {
					c = a + b;
					a = b;
					b = c;
				}
			}
			System.out.println( a + " " + b );
		}
		
	}

}

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		StringBuilder sb = new StringBuilder();
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt(), n, i;
		int dp[] = new int[41];
		dp[0] = 0;
		dp[1] = 1;
		for( i = 2; i <= 40; i++ )
			dp[i] = dp[i-1] + dp[i-2];
		while( t-- > 0 ) {
			n = sc.nextInt();
			if( n == 0 )
				sb.append( 1 + " " + 0 + "\n" );
			else 
				sb.append( dp[n-1] + " " + dp[n] + "\n" );
		}
		sc.close();
		System.out.println( sb.toString() );
	}
}